Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 15 of 15 for “"graph minor"”.

  1. Graph minor

    … Let G be a (k + 2)-connected non-(k - 3)-apex graph where k ≥ 2. If G contains three k-cliques, say L 1, L2, L3, such that |Li ∩ Lj| ≤ k - 2 (1 ≤ i < j ≤ 3), then G contains a Kk +2 as a minor. (2) Let G be a 6-connected claw-free graph. If delta(G) ≥ 7 and G contains three disjoint 5-cliques, …

    wvu Repository record for Graph minor (opens in a new tab)

  2. From graph minor theory to 3-dimensions

    … from topological combinatorics and structural graph theory. Firstly, we extend Heawood's theorem on the colourability of plane triangulations to triangulations of 3-space by proving that a triangulation of 3-space can be edge coloured with three colours if and only if all edges have even …

    birmingham Download PDF for From graph minor theory to 3-dimensions (opens in a new tab)

  3. Proof Theory of Graph Minors and Tree Embeddings

    … properties of theorems appearing in the Graph Minors series. A number of these theorems have been known to have very high proof-theoretic strength, but an upper bound on many of them, including the graph minor theorem, had never been proved. We give such upper bounds, by showing that any …

    whiterose Download PDF for Proof Theory of Graph Minors and Tree Embeddings (opens in a new tab)

  4. Graph minors and algorithms

    A graph H is a minor of another graph G, denoted by $H\ {\prec\sb{m}}\ G,$ if a graph isomorphic to H can be obtained from G by a series of vertex deletions, edge deletions, and edge contractions. Graph minors have been studied for several decades as a way of characterizing classes of graphs. …

    uiuc Repository record for Graph minors and algorithms (opens in a new tab)

  5. On the computability of obstruction sets for well-quasi-ordered graph classes

    … (ΘΕΓ), των Neil Robertson και Paul Seymour (Graph Minor Theorem) εγγυάται πως κάθε κλάση κλειστή ως προς τη σχέση των ελασσόνων έχει πεπερασμένο σύνολο παρεμόδησης. Αν η C είναι μια τέτοια κλάση, τότε το σύνολο παρεμπόδησης της C είναι το ελαχιστικό σύνολο γραφημάτων H έτσι ώστε, ένα γράφημα …

    athens Repository record for On the computability of obstruction sets for well-quasi-ordered graph classes (opens in a new tab)

  6. Μερικές διατάξεις και αλγόριθμοι σε γραφήματα

    In the Graph Minors project, N. Robertson and P. Seymour, proveda series of structural and algorithmic results. Some of them, such as theStrong and the Weak Structure Theorem, the Excluded Grid Theoremand the algorithm for Minor Containment, constitute a rich source ofmany more structural as well …

    greece Repository record for Μερικές διατάξεις και αλγόριθμοι σε γραφήματα (opens in a new tab)

  7. Unavoidable Immersions and Intertwines of Graphs

    The topological minor and the minor relations are well-studied binary relations on the class of graphs. A natural weakening of the topological minor relation is an immersion. An immersion of a graph H into a graph G is a map that injects the vertex set of H into the vertex set of G such that edges …

    lsu-thes Repository record for Unavoidable Immersions and Intertwines of Graphs (opens in a new tab)

  8. Διδιαστατότητα: θεωρία και αλγοριθμικές εφαρμογές

    … problem.Often these problems can be modeled by graphs. Then, additional structuralproperties of a graph, such as surface embeddability, can provide a handle forthe design of more ecient algorithms.The theory of Bidimensionality, dened in the context of ParameterizedComplexity, builds on the …

    greece Repository record for Διδιαστατότητα: θεωρία και αλγοριθμικές εφαρμογές (opens in a new tab)

  9. Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs

    … group. In this work, we restrict to the set of graph-LinBCS games, which arise from $\mathbb{Z}_2$-linear systems $Ax=b$, where $A$ is the incidence matrix of a connected graph, and $b$ is a (non-proper) vertex $2$-colouring. In this context, Arkhipov's theorem states that the corresponding …

    waterloo Repository record for Algebraic and combinatorial aspects of incidence groups and linear system non-local games arising from graphs (opens in a new tab)

  10. Graphs and geometry: an interplay between local and global views

    … dissertation, we explore problems related to graphs and geometry. This work consists of two projects, and they are independent and utilize distinct proof techniques. However, they share a common underlying philosophy: we alternate between local and global perspectives as required. In Project …

    gatech Repository record for Graphs and geometry: an interplay between local and global views (opens in a new tab)

  11. Minor-minimal non-projective planar graphs with an internal 3-separation

    The property that a graph has an embedding in the projective plane is closed under taking minors. Thus by the well known Graph Minor theorem of Robertson and Seymour, there exists a finite list of minor-minimal graphs, call it L, such that a given graph G is projective planar if and only if G does …

    gatech Repository record for Minor-minimal non-projective planar graphs with an internal 3-separation (opens in a new tab)

  12. Du atsitiktinių grafų modeliai /

    … doctoral dissertation \"On two models of random graphs\" (in English) by V. Kurauskas. We introduce the random graph models (random intersection graphs, graphs with disjoint excluded minors) studied in the thesis, overview the problems and state the main results.

    vilnius Repository record for Du atsitiktinių grafų modeliai / (opens in a new tab)

  13. Techniques for Crafting Customizable MPSoCS

    … loop kernels onto the reconfigurable fabric as a graph minor containment problem. With the formalization, we design an efficient search algorithm adopted from the graph theory domain to solve the mapping problem. As the final step of the design automation toolchain, we develop a design space …

    nus Repository record for Techniques for Crafting Customizable MPSoCS (opens in a new tab) Download file for Techniques for Crafting Customizable MPSoCS (opens in a new tab)

  14. Directed Graphs: Fixed-Parameter Tractability & Beyond

    Most interesting optimization problems on graphs are NP-hard, implying that (unless P=NP) there is no polynomial time algorithm that solves all the instances of an NP-hard problem exactly. However, classical complexity measures the running time as a function of only the overall input size. The …

    maryland Repository record for Directed Graphs: Fixed-Parameter Tractability & Beyond (opens in a new tab)

  15. A faster algorithm for torus embedding

    … a simple exponential algorithm for embedding graphs on the torus (a surface shaped like a doughnut) and discuss how it was inspired by the quadratic time planar embedding algorithm of Demoucron, Malgrange and Pertuiset. We show that it is faster in practice than the only fully implemented …

    uvic Repository record for A faster algorithm for torus embedding (opens in a new tab)