A Linear Time Algorithm for Minimum-Weight Feedback Vertex Set Problem in Outerplanar Graphs
Received:November 26, 2002  
Key Word: outerplanar graphs   feedback vertex set   linear time algorithm.  
Fund ProjectL:Supported by National Natural Science Found of China (60373025)
Author NameAffiliation
ZHANG Shao-qiang School of Comp. & Info. Engineering. Tianjin Normal University
Tianjin
China 
WANG Xiao-li School of Mathematics and Systems Science
Shandong University
Jinan
China
Dept. of Math.
Nanyang Normal University
Henan
China 
LI Guo-jun School of Mathematics and Systems Science
Shandong University
Jinan
China
Inst. of Software
Chinese Academy of Sciences
Beijing, China 
Hits: 1822
Download times: 798
Abstract:
      A subset of the vertex set of a graph is a feedback vertex set of the graph ifthe resulting graph is a forest after removing the vertex subset from the graph.In thispaper, we study the minimum-weight feedback vertex set problem in outerplanar graphs and present a linear time algorithm to solve it.
Citation:
DOI:10.3770/j.issn:1000-341X.2004.04.006
View Full Text  View/Add Comment  Download reader