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 20 of 29 for “"Graph minors"”.
-
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. …
-
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 …
-
Establishing a Connection Between Graph Structure, Logic, and Language Theory
The field of graph structure theory was given life by the Graph Minors Project of Robertson and Seymour, which developed many tools for understanding the way graphs relate to each other and culminated in the proof of the Graph Minors Theorem. One area of ongoing research in the field is attempting …
-
The Linkage Problem for Group-labelled Graphs
… thesis aims to extend some of the results of the Graph Minors Project of Robertson and Seymour to "group-labelled graphs". Let $\Gamma$ be a group. A $\Gamma$-labelled graph is an oriented graph with its edges labelled from $\Gamma$, and is thus a generalization of a signed graph. Our primary …
-
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 …
-
Cache scheduling
… is a special case of Cache Scheduling and is a graph problem that is closed under taking graph minors.
-
Μερικές διατάξεις και αλγόριθμοι σε γραφήματα
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 …
-
Local Structure for Vertex-Minors
… about a conjecture of Geelen on the structure of graphs with a forbidden vertex-minor; the conjecture is like the Graph Minors Structure Theorem of Robertson and Seymour but for vertex-minors instead of minors. We take a step towards proving the conjecture by determining the "local structure''. …
-
Connectivity, tree-decompositions and unavoidable-minors
… theorems known for minor-closed classes of graphs, and the very general, yet wildly qualitative, Graph Minors Structure Theorem. This thesis introduces a refinement of the notion of tree-width. Tree-width is a measure of how “tree-like” a graph is. Essentially, a graph is tree-like if it can …
-
Obstructions and algorithms for graph layouts problems
Modern Graph Theory is heavily influenced by the seminal work of N. Robertson and P. Seymour, known as Graph Minors. Through this work, a wealth of structural, combinatorial, as well as algorithmic, results has been introduced, in a series of papers having as ultimate goal to give an affirmative …
-
Decompositions and Algorithms for the Disjoint Paths Problem in Planar Graphs
… να συνδεθούν με διακεκριμένα μονοπάτια. Στα "Graph Minors", μια σειρά 23 εργασιών μεταξύ 1984 και 2011, οι Neil Robertson και Paul D. Seymour, ανάμεσα σε άλλα σπουδαία αποτελέσματα που επηρέασαν βαθιά την Θεωρία Γραφημάτων, παρουσίασαν έναν f(k)*n^3 αλγόριθμο για το πρόβλημα των Διακεκριμενων …
-
On the computability of obstruction sets for well-quasi-ordered graph classes
… (ΘΕΓ), των Neil Robertson και Paul Seymour (Graph Minor Theorem) εγγυάται πως κάθε κλάση κλειστή ως προς τη σχέση των ελασσόνων έχει πεπερασμένο σύνολο παρεμόδησης. Αν η C είναι μια τέτοια κλάση, τότε το σύνολο παρεμπόδησης της C είναι το ελαχιστικό σύνολο γραφημάτων H έτσι ώστε, ένα γράφημα …
-
Cyclability: combinatorial properties, algorithms and complexity
A graph G is called k-cyclable, if for every k of its vertices there exists a cycle in G that contains them. The cyclability of G is the maximum integer k for which G is k-cyclable and it is a connectivity related graph parameter. In this doctoral thesis we study, mainly from the Parameterized …
-
Integer programming models for the branchwidth problem
… and an optimal branch decomposition of a graph. Branch decompositions and branchwidth were introduced in 1991 by Robertson and Seymour and were used in the proof of Graph Minors Theorem (GMT), a well known conjecture (Wagner's conjecture) in graph theory. The notions of branchwidth and …
-
Connected matchings in special families of graphs.
A connected matching in a graph is a set of disjoint edges such that, for any pair of these edges, there is another edge of the graph incident to both of them. This dissertation investigates two problems related to finding large connected matchings in graphs. The first problem is motivated by a …
-
The Extremal Function for K10 Minors
We prove that every graph on n >= 8 vertices and at least 8n-35 edges either has a K10 minor or is isomorphic to some graph included in a few families of exceptional graphs.
-
Extremal graph theory: Ramsey-Turán numbers, chromatic thresholds, and minors
… investigates several questions in extremal graph theory and the theory of graph minors. It consists of three independent parts; the first two parts focus on questions motivated by Turan's Theorem and the third part investigates a problem related to Hadwiger's Conjecture. Let H be a graph, t …
-
New Tools and Results in Graph Structure Theory
… extensions' theorem for polyhedral graph embeddings. Let G be a ``weakly 4-connected' planar graph. We describe a set of constructions that produce a finite list of non-planar graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has …
-
Some Results on Seymour’s Second-Neighborhood Conjecture and on Decompositions of Graphs
… states that every orientation of every simple graph has at least one vertex v such that the number of vertices of out-distance 2 from v is at least as large as the number of vertices of out-distance 1 from it. I present alternative statements of this conjecture using the language of linear …
-
Extremal Functions for Graph Linkages and Rooted Minors
Extremal Functions for Graph Linkages and Rooted Minors Paul Wollan 137 pages Directed by: Robin Thomas A graph G is k-linked if for any 2k distinct vertices s_1,..., s_k,t_1,..., t_k there exist k vertex disjoint paths P_1,...,P_k such that the endpoints of P_i are s_i and t_i. Determining the …
Page 1 of 2