On feedback vertex set new measure and new structures

DOI10.1007/978-3-642-13731-0_10MaRDI QIDQ3569882zbMATH OpenOpenAlexFDO

Authors Yixin Cao, Yang Liu, Jianer 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

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

Recommendations

• On feedback vertex set: new measure and new structures
• Parameterized and Exact Computation
• Faster fixed parameter tractable algorithms for finding feedback vertex sets
• An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
• Computing and Combinatorics

Cited in

(31)

• Parameterised algorithms for deletion to classes of DAGs
• Towards a polynomial kernel for directed feedback vertex set
• Towards a polynomial kernel for directed feedback vertex set
• scientific article; zbMATH DE number 7286685 (Why is no real title available?)
• On parameterized independent feedback vertex set
• Circular convex bipartite graphs: feedback vertex set
• Proper interval vertex deletion
• Enumerating minimal subset feedback vertex sets
• An improved FPT algorithm and quadratic kernel for pathwidth one vertex deletion
• Circular convex bipartite graphs: feedback vertex sets
• Chordal editing is fixed-parameter tractable
• Feedback vertex sets on restricted bipartite graphs
• A quartic kernel for pathwidth-one vertex deletion
• FPT algorithms for connected feedback vertex set
• Linear time parameterized algorithms for subset feedback vertex set
• An improved parameterized algorithm for the independent feedback vertex set problem
• Guarantees and limits of preprocessing in constraint satisfaction and reasoning
• A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem
• An improved exact algorithm for undirected feedback vertex set
• Refining the complexity of the sports elimination problem
• Proper Interval Vertex Deletion
• An Improved Exact Algorithm for Undirected Feedback Vertex Set
• Kernels for deletion to classes of acyclic digraphs
• Parameterized and Exact Computation
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• On feedback vertex set: new measure and new structures
• Structural Parameterizations of Feedback Vertex Set
• Faster deterministic \textsc{Feedback Vertex Set}
• Two Hardness Results on Feedback Vertex Sets
• An improved FPT algorithm and a quadratic kernel for pathwidth one vertex deletion
• On making a distinguished vertex of minimum degree by vertex deletion

This page was built for publication: On feedback vertex set new measure and new structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3569882)