A linear time algorithm for the minimum-weight feedback vertex set problem in series-parallel graphs

DOI10.1007/S10255-004-0195-6MaRDI QIDQ705040zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

feedback vertex setseries-parallel graphlinear algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

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

Cites work

• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 1305449 (Why is no real title available?)
• scientific article; zbMATH DE number 1443271 (Why is no real title available?)
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference
• Easy problems for tree-decomposable graphs
• Graph theory with applications
• Steiner \(k\)-edge connected subgraph polyhedra

Cited in

(6)

• scientific article; zbMATH DE number 2163938 (Why is no real title available?)
• 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 weighted feedback vertex problem on interval graphs
• A linear time algorithm for the minimum weighted feedback vertex set on diamonds
• 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)