A Linear Time Algorithm for Minimum-Weight Feedback Vertex Set Problem in Outerplanar Graphs
Received:November 26, 2002  
Key Words: outerplanar graphs   feedback vertex set   linear time algorithm.  
Fund Project: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: 2465
Download times: 1096
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  
  Copyright © Journal of Mathematical Research with Applications
Sponsored by：Dalian University of Technology, China Society for Industrial and Applied Mathematics
Address：No.2 Linggong Road, Ganjingzi District, Dalian City, Liaoning Province, P. R. China , Postal code ：116024
Service Tel：86-411-84707392 Email：jmre@dlut.edu.cn
Designed by Beijing E-tiller Co.,Ltd.
Due to security factors, early browsers cannot log in. It is recommended to log in with IE10, IE11, Google, Firefox, and 360 new browsers.