期刊论文

Feng, Qilong

英文

Information Processing Letters

0020-0190

2018

136

30-36

10.1016/j.ipl.2018.03.016

This work is supported by the National Natural Science Foundation of China under Grants (61472449, 61772179, 61420106009, 61402054, 61572414, 71631008), the Scientific Research Fund of Hunan Provincial Education Department under Grant (17C0222), the Hengyang Foundation for Development of Science and Technology under Grant (2016KG39), the Science and Technology Plan Project of Hunan Province under Grants (2016TP1020) and the Open Fund Project of Hunan Provincial Key Laboratory of Intelligent Information Processing and Application for Hengyang Normal University.

本校为其他机构

Almost Forest Deletion problem (AFD) is a generalization of the Feedback Vertex Set problem, which decides whether there exist at most k vertices in a given graph G whose removal from G results in an l-forest, where k and l are two given non-negative integers, and an l-forest is a graph which can be transformed into a forest by deleting at most l edges. Based on the iterative compression technique, we study the iterative version of the AFD problem, called Almost Forest Deletion Disjoint Compression problem (AFDDC), which asks for a new l-forest...