Optimal algorithms for hitting (topological) minors on graphs of bounded treewidth
DOI10.4230/LIPICS.IPEC.2017.4zbMATH Open1443.68120MaRDI QIDQ5111863FDOQ5111863
Authors: Julien Baste, Ignasi Sau, 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
- Hitting forbidden minors: approximation and kernelization
- Lower bounds based on the exponential time hypothesis
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Bidimensionality and kernels
- 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
- 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 (12)
- Modification to Planarity is Fixed Parameter Tractable
- Compactors for parameterized counting problems
- Hitting minors on bounded treewidth graphs. I: General upper bounds
- A complexity dichotomy for hitting connected minors on bounded treewidth graphs: the chair and the banner draw the boundary
- 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
- A complexity dichotomy for hitting small planar minors parameterized by treewidth
- Hitting minors on bounded treewidth graphs. II. Single-exponential algorithms
- A single-exponential FPT algorithm for the \(K _{4}\)-minor cover problem
- Hitting forbidden induced subgraphs on bounded treewidth graphs
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)
