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

DOI10.1007/s10255-004-0195-6zbMath1055.05146OpenAlexW2056194369MaRDI QIDQ705040

Shaoqiang Zhang, Shuguang Li, Guo Jun 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

series-parallel graphfeedback vertex setlinear algorithm

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Steiner \(k\)-edge connected subgraph polyhedra
• Easy problems for tree-decomposable graphs
• Approximation Algorithms for the Feedback Vertex Set Problem with Applications to Constraint Satisfaction and Bayesian Inference