Graph minors and parameterized algorithm design
From MaRDI portal
Publication:2908540
DOI10.1007/978-3-642-30891-8_13zbMATH Open1358.68314OpenAlexW58268685MaRDI QIDQ2908540FDOQ2908540
Authors: Dimitrios M. Thilikos
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
Recommendations
Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Graph minors (05C83)
Cites Work
- Parameterized complexity of vertex deletion into perfect graph classes
- Planarity Allowing Few Error Vertices in Linear Time
- Outerplanar obstructions for matroid pathwidth
- Title not available (Why is that?)
- An improved algorithm for the half-disjoint paths problem
- Graph minors. X: Obstructions to tree-decomposition
- Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Graph minors. XX: Wagner's conjecture
- Graph minors. XIII: The disjoint paths problem
- Hitting forbidden minors: approximation and kernelization
- Easy problems for tree-decomposable graphs
- Title not available (Why is that?)
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Title not available (Why is that?)
- Graph minors. V. Excluding a planar graph
- Highly connected sets and the excluded grid theorem
- Quickly excluding a planar graph
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Odd cycle packing
- Graph minors. II. Algorithmic aspects of tree-width
- Courcelle's theorem -- a game-theoretic approach
- The disjoint paths problem in quadratic time
- (Meta) Kernelization
- Bidimensionality and kernels
- Approximation algorithms for treewidth
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Graph minor theory
- Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
- Polynomial treewidth forces a large grid-like-minor
- Title not available (Why is that?)
- On the existence of subexponential parameterized algorithms
- Subexponential algorithms for partial cover problems
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Subexponential parameterized algorithms on bounded-genus graphs and \(H\)-minor-free graphs
- Dynamic Programming and Fast Matrix Multiplication
- Graph minors. I. Excluding a forest
- Minimal acyclic forbidden minors for the family of graphs with bounded path-width
- The vertex separation and search number of a graph
- Algorithms and obstructions for linear-width and related search parameters
- Beyond NP-completeness for problems of bounded width: hardness for the W hierarchy (extended abstract)
- Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
- Directed Nowhere Dense Classes of Graphs
- Chordal deletion is fixed-parameter tractable
- Graph minors. III. Planar tree-width
- Domination problems in nowhere-dense classes of graphs
- Bidimensionality: new connections between FPT algorithms and PTASs
- Fourier meets M\"{o}bius: fast subset convolution
- Title not available (Why is that?)
- Graph minors. XXI. graphs with unique linkages
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- Experimental evaluation of a tree decomposition-based algorithm for vertex cover on planar graphs
- The complexity of first-order and monadic second-order logic revisited
- Tight bounds for linkages in planar graphs
- Graph minors. XXII. Irrelevant vertices in linkage problems
- Finding topological subgraphs is fixed-parameter tractable
- On Ordered Division Rings
- Graph minors XXIII. Nash-Williams' immersion conjecture
- On search, decision, and the efficiency of polynomial-time algorithms
- The Structure and Number of Obstructions to Treewidth
- On the excluded minors for the matroids of branch-width \(k\)
- Induced Packing of Odd Cycles in a Planar Graph
- Towards fully multivariate algorithmics: some new results and directions in parameter ecology
- Ordering by Divisibility in Abstract Algebras
- Obtaining a bipartite graph by contracting few edges
- Title not available (Why is that?)
- On computing graph minor obstruction sets
- Contraction obstructions for treewidth
- Obtaining a planar graph by vertex deletion
- Contraction checking in graphs on surfaces
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Linearity of grid minors in treewidth with applications through bidimensionality
- Tree decompositions of graphs: saving memory in dynamic programming
- Title not available (Why is that?)
- Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
- On obstructions to small face covers in planar graphs
- Graph minors. XVII: Taming a vortex
- Outerplanar obstructions for the feedback vertex set
- Obstructions for tree-depth
- Title not available (Why is that?)
- Title not available (Why is that?)
- Bidimensional Parameters and Local Treewidth
- A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
- Linkless and flat embeddings in 3-space and the unknot problem
- Well-Quasi-Ordering, The Tree Theorem, and Vazsonyi's Conjecture
- Improved bounds on the planar branchwidth with respect to the largest grid minor size
- Title not available (Why is that?)
- Dynamic programming for graphs on surfaces
- Fast Subexponential Algorithm for Non-local Problems on Graphs of Bounded Genus
- The Bidimensional Theory of Bounded-Genus Graphs
- The structure of obstructions to treewidth and pathwidth
- A Practical Approach to Courcelle's Theorem
- Parameterizing cut sets in a graph by the number of their components
- The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs
- Title not available (Why is that?)
- Girths of bipartite sextet graphs
- Recognizing a totally odd \(K_{4}\)-subdivision, parity 2-disjoint rooted paths and a parity cycle through specified elements
- The NP-completeness column: An ongoing guide
- Fast minor testing in planar graphs
- Hadwiger's conjecture is decidable
- Upper bounds on the size of obstructions and intertwines
- Title not available (Why is that?)
Cited In (16)
- Compactors for parameterized counting problems
- A Retrospective on (Meta) Kernelization
- Parameterized computational geometry via decomposition theorems
- Contraction bidimensionality of geometric intersection graphs
- Title not available (Why is that?)
- Elimination Distance to Bounded Degree on Planar Graphs
- \(k\)-apices of minor-closed graph classes. I: Bounding the obstructions
- Contraction-bidimensionality of geometric intersection graphs
- Elimination distance to bounded degree on planar graphs preprint
- A Simple Algorithm for the Graph Minor Decomposition − Logic meets Structural Graph Theory–
- Title not available (Why is that?)
- A Linear-Time Algorithm for Finding a Complete Graph Minor in a Dense Graph
- Dynamic Programming for H-minor-free Graphs
- Combing a Linkage in an Annulus
- Quickly deciding minor-closed parameters in general graphs
- Bidimensionality and kernels
This page was built for publication: Graph minors and parameterized algorithm design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2908540)