|
|||||
|
|
A Linear Time Algorithm for the Minimum-weight Feedback Vertex Set Problem in Series-parallel Graphs |
|
| Authors: | |
| Institution: | (1) College of Computer and Information Engineering, Tianjin Normal University, Tianjin, 300074, China;(2) Institute of Software, CAS, Beijing, 100080, China;(3) School of Mathematics and System Sciences, Shandong University, Jinan, 250100, China;(4) Department of Mathematics and Information Science, Yantai University, Yantai, 264005, China |
| Abstract: | Abstract A feedback vertex set is a subset of vertices in a graph, whose deletion from the graph makes the resulting graph acyclic. In this paper, we study the minimum-weight feedback vertex set problem in series-parallel graphs and present a linear-time exact algorithm to solve it. Supported by the National Science Foundation of China (No.10271065, 60373025). |
| Keywords: | Series-parallel graph feedback vertex set linear algorithm |
| 本文献已被 维普 SpringerLink 等数据库收录！ | |