A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
DOI10.1007/S10255-004-0195-6zbMATH Open1055.05146OpenAlexW2056194369MaRDI QIDQ705040FDOQ705040
Authors: Shaoqiang Zhang, Shu-Guang Li, Guojun Li 
Publication date: 25 January 2005
Published in: Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10255-004-0195-6
Recommendations
- scientific article; zbMATH DE number 2163938
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- On the feedback vertex set polytope of a series-parallel graph
- A linear time algorithm for the minimum weighted feedback vertex set on diamonds
- A linear time algorithm to solve the weighted perfect domination problem in series-parallel graphs
- Linear time parameterized algorithms for subset feedback vertex set
- Parallelism and the feedback vertex set problem
- Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}
- On the minimum feedback vertex set problem: Exact and enumeration algorithms
- A linear time algorithm for a variant of the MAX CUT problem in series parallel graphs
Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
- Graph theory with applications
- Easy problems for tree-decomposable graphs
- Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
- Title not available (Why is that?)
- Steiner \(k\)-edge connected subgraph polyhedra
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (6)
- Title not available (Why is that?)
- Minimum weight feedback vertex sets in circle graphs
- On the feedback vertex set polytope of a series-parallel graph
- A linear time algorithm for the minimum weighted feedback vertex set on diamonds
- A linear-time algorithm for the weighted feedback vertex problem on interval graphs
- Two feedback problems for graphs with bounded tree-width
This page was built for publication: A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q705040)
