Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
From MaRDI portal
Publication:5252660
DOI10.1137/120892234zbMath1314.05134OpenAlexW2037713618MaRDI QIDQ5252660
Publication date: 2 June 2015
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/120892234
Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)
Related Items
Isomorphism Testing for Graphs Excluding Small Minors, Excluding subdivisions of bounded degree graphs, Designing FPT Algorithms for Cut Problems Using Randomized Contractions, Minors and dimension, An improved isomorphism test for bounded-tree-width graphs, Layered separators in minor-closed graph classes with applications, A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three, Order Reconfiguration under Width Constraints, Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth, Packing topological minors half‐integrally, Long induced paths in minor-closed graph classes and beyond, A Faster Isomorphism Test for Graphs of Small Degree, Induced subgraphs and tree decompositions. VII: Basic obstructions in \(H\)-free graphs, Isomorphism Testing Parameterized by Genus and Beyond, Induced minor free graphs: isomorphism and clique-width, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Minimum Bisection Is Fixed-Parameter Tractable, Improved Bounds for Centered Colorings, Turing kernelization for finding long paths in graph classes excluding a topological minor, Unnamed Item, A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors, Computing with Tangles, Parameterized Complexity of Directed Steiner Tree on Sparse Graphs, A Structure Theorem for Strong Immersions, Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor, Canonisation and Definability for Graphs of Bounded Rank Width
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Implicit branching and parameterized partial cover problems
- Graph minors. XX: Wagner's conjecture
- Parameterized graph separation problems
- Some recent progress and applications in graph minor theory
- Isomorphism of graphs of bounded valence can be tested in polynomial time
- Graph minors. X: Obstructions to tree-decomposition
- Graph minors. XVI: Excluding a non-planar graph
- Graph minors. XIII: The disjoint paths problem
- Local tree-width, excluded minors, and approximation algorithms
- Homomorphieeigenschaften und mittlere Kantendichte von Graphen
- A shorter proof of the graph minor algorithm
- Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs
- Edge-disjoint paths in Planar graphs with constant congestion
- Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth
- Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
- Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus
- Divide-and-Color
- Descriptive Complexity, Canonisation, and Definable Graph Structure Theory
- Fixed-point definability and polynomial time on graphs with excluded minors
- Contraction decomposition in h-minor-free graphs and algorithmic applications
- A simpler algorithm and shorter proof for the graph minor decomposition
- Finding topological subgraphs is fixed-parameter tractable
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
