Graph minors and parameterized algorithm design

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

• Algorithmic Graph Minors and Bidimensionality
• Bidimensionality and parameterized algorithms (invited talk)
• scientific article; zbMATH DE number 795221
• Subexponential parameterized algorithms
• scientific article; zbMATH DE number 2079336

zbMATH Keywords

treewidthgraph minorslinkagesparameterized algorithmsbidimensionalityirrelevant vertex technique

Mathematics Subject Classification ID

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)