期刊论文、会议论文

Feng, Qilong

英文

Lecture Notes in Computer Science

0302-9743

2018

10976

726-737

24th International Computing and Combinatorics Conference (COCOON)

Lecture Notes in Computer Science

JUL 02-04, 2018

Qing Dao, PEOPLES R CHINA

[Lin, Mugang;Feng, Qilong] Cent S Univ, Sch Informat Sci & Engn, Changsha, Hunan, Peoples R China.^[Lin, Mugang] Hengyang Normal Univ, Sch Comp Sci & Technol, Hengyang, Peoples R China.^[Lin, Mugang] Hunan Prov Key Lab Intelligent Informat Proc & Ap, Hengyang, Peoples R China.^[Fu, Bin] Univ Texas Rio Grande Valley, Dept Comp Sci, Edinburg, TX 78539 USA.

Wang, L Zhu, D

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

978-3-319-94776-1; 978-3-319-94775-4

10.1007/978-3-319-94776-1_60

National Natural Science Foundation of ChinaNational Natural Science Foundation of China (NSFC) [61772179, 61472449, 61420106009, 61402054]; Science and Technology Plan Project of Hunan Province [2016TP1020]; Scientific Research Fund of Hunan Provincial Education DepartmentHunan Provincial Education Department [17C0222]

本校为其他机构

An l-pseudoforest is a graph each of whose connected component is at most l edges away from being a tree. The l-Pseudoforest Deletion problem is to delete a vertex set P of minimum weight from a given vertex-weighted graph \(G=(V,E)\) such that the remaining graph \(G[V\setminus P]\) is an l-pseudoforest. The Feedback Vertex Set problem is a special case of the l-Pseudoforest Deletion problem with \(l=0\). In this paper, we present a polynomial time 4l-approximation algorithm for the l-Pseudoforest Deletion problem with \(l\ge 1\) by using the local ratio technique. When \(l=1\), we get a bett...