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 6 of 6 for “"Graph minor theory"”.
-
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 …
-
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. …
-
Μερικές διατάξεις και αλγόριθμοι σε γραφήματα
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 …
-
Διδιαστατότητα: θεωρία και αλγοριθμικές εφαρμογές
… 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 …
-
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 …
-
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 …