๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs

โœ Scribed by Shao-qiang Zhang; Guo-jun Li; Shu-guang Li

Publisher
Institute of Applied Mathematics, Chinese Academy of Sciences and Chinese Mathematical Society
Year
2004
Tongue
English
Weight
169 KB
Volume
20
Category
Article
ISSN
0168-9673

No coin nor oath required. For personal study only.

๐Ÿ“œ SIMILAR VOLUMES

A linear-time algorithm for the weighted
A linear-time algorithm for the weighted feedback vertex problem on interval graphs
โœ Chin Lung Lu; Chuan Yi Tang ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 459 KB

We present a linear-time algorithm for finding a minimum weighted feedback vertex set on interval graphs using the dynamic programming technique. Since the weighted feedback vertex problem, the weighted C3.1 problem, the maximum weighted 2-colorable subgraph problem and the maximum weighted 2-indepe

A linear time algorithm for computing th
A linear time algorithm for computing the most reliable source on a series-parallel graph with unreliable edges
โœ Charles J. Colbourn; Guoliang Xue ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 993 KB

Given a network with n vertices and m edges where each edge has an independent operational probability, we are interested in finding a vertex of the network whose expected number of reachable vertices is maximum. Such a vertex is called a most reliable source of the network. This problem was studied