On feedback vertex set new measure and new structures

DOI10.1007/978-3-642-13731-0_10zbMATH Open1285.68061OpenAlexW1826506799MaRDI QIDQ3569882FDOQ3569882

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

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

Mathematics Subject Classification ID

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

Cited In (30)

• 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
• Title not available (Why is that?)
• 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
• 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)