期刊论文、会议论文

Feng, Qilong

英文

Lecture Notes in Computer Science

0302-9743

2018

10976 LNCS

726-737

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

This work is supported by the National Natural Science Foundation of China under Grants (61772179, 61472449, 61420106009, 61402054), the Science and Technology Plan Project of Hunan Province under Grant (2016TP1020) and the Scientific Research Fund of Hunan Provincial Education Department under Grant (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 (Formula Presented) such that the remaining graph (Formula Presented) is an l-pseudoforest. The Feedback Vertex Set problem is a special case of the l-Pseudoforest Deletion problem with (Formula Presented). In this paper, we present a polynomial time 4l-approximation algorithm for the l-Pseudoforest Deletion problem with (For...