A Quartic Kernel for Pathwidth-One Vertex Deletion

DOI10.1007/978-3-642-16926-7_19zbMath1309.68100arXiv1009.0806OpenAlexW2134469776MaRDI QIDQ3057625

Yngve Villanger, Geevarghese Philip, Venkatesh Raman

Publication date: 16 November 2010

Published in: Graph Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.0806

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Faster algorithm for pathwidth one vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ Contracting graphs to paths and trees ⋮ Parameterized complexity of Eulerian deletion problems ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Faster deterministic algorithms for \textsc{Co-path Packing} and \textsc{Co-path/cycle Packing} ⋮ Preprocessing for outerplanar vertex deletion: an elementary kernel of quartic size ⋮ Modifying a graph using vertex elimination

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Subexponential parameterized algorithms
• Compression-based fixed-parameter algorithms for feedback vertex set and edge bipartization
• Graph bandwidth of weighted caterpillars
• A cubic kernel for feedback vertex set and loop cutset
• Graph minors. I. Excluding a forest
• The node-deletion problem for hereditary properties is NP-complete
• The NP-completeness of the bandwidth minimization problem
• A partial k-arboretum of graphs with bounded treewidth
• Obstruction set isolation for the gate matrix layout problem
• Treewidth. Computations and approximations
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• A Quartic Kernel for Pathwidth-One Vertex Deletion
• An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion
• The Proper Interval Colored Graph problem for caterpillar trees
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Treewidth: Characterizations, Applications, and Computations
• On Feedback Vertex Set New Measure and New Structures
• A Cubic Kernel for Feedback Vertex Set
• Graph minors. II. Algorithmic aspects of tree-width
• The Bandwidth of Caterpillars with Hairs of Length 1 and 2
• ON DISJOINT CYCLES
• A 2-Approximation Algorithm for the Undirected Feedback Vertex Set Problem
• Parameterized and Exact Computation

This page was built for publication: A Quartic Kernel for Pathwidth-One Vertex Deletion