On Feedback Vertex Set New Measure and New Structures

DOI10.1007/978-3-642-13731-0_10zbMath1285.68061OpenAlexW1826506799MaRDI QIDQ3569882

Yixin Cao, Yang Liu, Jian'er Chen

Publication date: 22 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-13731-0_10

Mathematics Subject Classification ID

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

Related Items (31)

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set ⋮ Circular convex bipartite graphs: feedback vertex sets ⋮ Chordal editing is fixed-parameter tractable ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Feedback vertex sets on restricted bipartite graphs ⋮ Refining the complexity of the sports elimination problem ⋮ Proper interval vertex deletion ⋮ Contracting graphs to paths and trees ⋮ Guarantees and limits of preprocessing in constraint satisfaction and reasoning ⋮ An improved parameterized algorithm for the independent feedback vertex set problem ⋮ Enumerating minimal subset feedback vertex sets ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ On parameterized independent feedback vertex set ⋮ On making a distinguished vertex of minimum degree by vertex deletion ⋮ An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion ⋮ FPT algorithms for connected feedback vertex set ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ An Improved FPT Algorithm and Quadratic Kernel for Pathwidth One Vertex Deletion ⋮ Proper Interval Vertex Deletion ⋮ Unnamed Item ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Unnamed Item ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ Circular Convex Bipartite Graphs: Feedback Vertex Set ⋮ Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth ⋮ An improved exact algorithm for undirected feedback vertex set ⋮ On group feedback vertex set parameterized by the size of the cutset

This page was built for publication: On Feedback Vertex Set New Measure and New Structures