A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem

DOI10.1016/j.jcss.2014.05.001zbMath1357.68289OpenAlexW1667353902MaRDI QIDQ743120

Geevarghese Philip, Eun Jung Kim, Christophe Paul

Publication date: 22 September 2014

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2014.05.001

zbMATH Keywords

fixed-parameter tractable algorithms\(K_4\)-Minor CoverTreewidth-2 Deletion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Quick but odd growth of cacti ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds

Uses Software

• Algorithm 447

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Graph minors. XX: Wagner's conjecture
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Improved algorithms for feedback vertex set problems
• The node-deletion problem for hereditary properties is NP-complete
• Parallel recognition of series-parallel graphs
• A partial k-arboretum of graphs with bounded treewidth
• Treewidth. Computations and approximations
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Parametrized complexity theory.
• Tight lower bounds for certain parameterized NP-hard problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Subexponential parameterized algorithms on bounded-genus graphs and H -minor-free graphs
• On Feedback Vertex Set New Measure and New Structures
• The Recognition of Series Parallel Digraphs
• Parallel algorithms for series parallel graphs
• Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
• (Meta) Kernelization
• A Near-Optimal Planarization Algorithm
• Bidimensionality and Geometric Graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Hitting and Harvesting Pumpkins

This page was built for publication: A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem