Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
DOI10.4230/LIPICS.IPEC.2017.4zbMATH Open1443.68120MaRDI QIDQ5111863FDOQ5111863
Ignasi Sau, Julien Baste, Dimitrios M. Thilikos
Publication date: 27 May 2020
Recommendations
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- A complexity dichotomy for hitting small planar minors parameterized by treewidth
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
dynamic programmingtreewidthexponential time hypothesisgraph minorsparameterized complexitytopological minorshitting minors
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Graph minors (05C83) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Graph minors. X: Obstructions to tree-decomposition
- The node-deletion problem for hereditary properties is NP-complete
- Which problems have strongly exponential complexity?
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Bidimensionality and Geometric Graphs
- Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
- Title not available (Why is that?)
- Explicit Linear Kernels via Dynamic Programming
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- (Meta) Kernelization
- A Near-Optimal Planarization Algorithm
- Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems
- On the number of labeled graphs of bounded treewidth
- A tight lower bound for vertex planarization on graphs of bounded treewidth
- Deleting vertices to bound path length
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
Cited In (8)
- Modification to Planarity is Fixed Parameter Tractable
- Compactors for parameterized counting problems
- Hitting minors on bounded treewidth graphs. III. Lower bounds
- Local tree-width, excluded minors, and approximation algorithms
- A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
- Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
- Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
This page was built for publication: Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111863)
