On Feedback Vertex Set New Measure and New Structures

DOI10.1007/978-3-642-13731-0_10zbMath1285.68061MaRDI 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

68Q25: Analysis of algorithms and problem complexity

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

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