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"”.
-
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, …
-
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 …
-
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 …
-
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. …
-
On the computability of obstruction sets for well-quasi-ordered graph classes
… (ΘΕΓ), των Neil Robertson και Paul Seymour (Graph Minor Theorem) εγγυάται πως κάθε κλάση κλειστή ως προς τη σχέση των ελασσόνων έχει πεπερασμένο σύνολο παρεμόδησης. Αν η C είναι μια τέτοια κλάση, τότε το σύνολο παρεμπόδησης της C είναι το ελαχιστικό σύνολο γραφημάτων H έτσι ώστε, ένα γράφημα …
-
Μερικές διατάξεις και αλγόριθμοι σε γραφήματα
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 …
-
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 …
-
Διδιαστατότητα: θεωρία και αλγοριθμικές εφαρμογές
… 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 …
-
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 …
-
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 …
-
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 …
-
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.
-
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 …
-
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 …
-
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 …