Graph Minors and Parameterized Algorithm Design
From MaRDI portal
Publication:2908540
DOI10.1007/978-3-642-30891-8_13zbMath1358.68314OpenAlexW58268685MaRDI QIDQ2908540
Publication date: 5 September 2012
Published in: The Multivariate Algorithmic Revolution and Beyond (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-30891-8_13
Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (8)
Compactors for parameterized counting problems ⋮ A Retrospective on (Meta) Kernelization ⋮ Contraction bidimensionality of geometric intersection graphs ⋮ \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions ⋮ Combing a Linkage in an Annulus ⋮ Bidimensionality and Kernels ⋮ Elimination Distance to Bounded Degree on Planar Graphs ⋮ Contraction-Bidimensionality of Geometric Intersection Graphs
Cites Work
- Courcelle's theorem -- a game-theoretic approach
- The disjoint paths problem in quadratic time
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Parameterizing cut sets in a graph by the number of their components
- Polynomial treewidth forces a large grid-like-minor
- Graph minors. XX: Wagner's conjecture
- Graph minors. III. Planar tree-width
- Approximation algorithms for treewidth
- Linearity of grid minors in treewidth with applications through bidimensionality
- Graph minors XXIII. Nash-Williams' immersion conjecture
- Chordal deletion is fixed-parameter tractable
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- Graph minors. XXI. graphs with unique linkages
- Graph minors. I. Excluding a forest
- Girths of bipartite sextet graphs
- Graph minors. V. Excluding a planar graph
- Graph minors. X: Obstructions to tree-decomposition
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- On obstructions to small face covers in planar graphs
- Upper bounds on the size of obstructions and intertwines
- Highly connected sets and the excluded grid theorem
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- The vertex separation and search number of a graph
- Quickly excluding a planar graph
- On search, decision, and the efficiency of polynomial-time algorithms
- On the excluded minors for the matroids of branch-width \(k\)
- Graph minors. XVII: Taming a vortex
- On computing graph minor obstruction sets
- Algorithms and obstructions for linear-width and related search parameters
- The structure of obstructions to treewidth and pathwidth
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On the existence of subexponential parameterized algorithms
- The complexity of first-order and monadic second-order logic revisited
- Graph minors. XIII: The disjoint paths problem
- Subexponential algorithms for partial cover problems
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- Contraction obstructions for treewidth
- Obtaining a planar graph by vertex deletion
- Tree decompositions of graphs: saving memory in dynamic programming
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Beyond NP-completeness for problems of bounded width (extended abstract)
- Outerplanar Obstructions for the Feedback Vertex Set
- Obstructions for Tree-depth
- Odd cycle packing
- Domination Problems in Nowhere-Dense Classes
- Tight Bounds for Linkages in Planar Graphs
- Improved Bounds on the Planar Branchwidth with Respect to the Largest Grid Minor Size
- Parameterized Complexity of Vertex Deletion into Perfect Graph Classes
- The Structure and Number of Obstructions to Treewidth
- An Improved Algorithm for the Half-Disjoint Paths Problem
- Easy problems for tree-decomposable graphs
- Graph minor theory
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- The Bidimensional Theory of Bounded-Genus Graphs
- Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
- Fourier meets M\"{o}bius: fast subset convolution
- Fast Minor Testing in Planar Graphs
- Dynamic Programming for Graphs on Surfaces
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Towards Fully Multivariate Algorithmics: Some New Results and Directions in Parameter Ecology
- Induced Packing of Odd Cycles in a Planar Graph
- Graph minors. II. Algorithmic aspects of tree-width
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- A Practical Approach to Courcelle's Theorem
- (Meta) Kernelization
- Planarity Allowing Few Error Vertices in Linear Time
- Hadwiger's conjecture is decidable
- Bidimensional Parameters and Local Treewidth
- Linkless and flat embeddings in 3-space and the unknot problem
- Directed Nowhere Dense Classes of Graphs
- Bidimensionality and Geometric Graphs
- Finding topological subgraphs is fixed-parameter tractable
- Dynamic Programming and Fast Matrix Multiplication
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- On Ordered Division Rings
- Ordering by Divisibility in Abstract Algebras
- The NP-completeness column: An ongoing guide
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Graph Minors and Parameterized Algorithm Design
