Kernelization and Parameterized Algorithms for 3-Path Vertex Cover

被引：9

作者：

Xiao, Mingyu ^{[1
]}

Kou, Shaowei ^{[1
]}

机构：

[1] Univ Elect Sci & Technol China, Sch Comp Sci & Engn, Chengdu 611731, Sichuan, Peoples R China

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2017) | 2017年 / 10185卷

基金：

中国国家自然科学基金;

关键词：

DISSOCIATION NUMBER; PATH COVER; COMPLEXITY; GRAPH; SET;

D O I：

10.1007/978-3-319-55911-7_47

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A 3-path vertex cover in a graph is a vertex subset C such that every path of three vertices contains at least one vertex from C. The parameterized 3-path vertex cover problem asks whether a graph has a 3-path vertex cover of size at most k. In this paper, we give a kernel of 5 k vertices and an O*(1.7485(k))-time algorithm for this problem, both new results improve previous known bounds.

引用

页码：653 / 667

页数：15

共 29 条

[1]

Abu-Khzam Faisal N., 2004, P 6 WORKSHOP ALGORIT, P62

[2] NP-hard graph problems and boundary classes of graphs [J].

Alekseev, V. E. ;

Boliac, R. ;

Korobitsyn, D. V. ;

Lozin, V. V. .

THEORETICAL COMPUTER SCIENCE, 2007, 389 (1-2) :219-236

[3] An optimal parallel solution for the path cover problem on P4-sparse graphs [J].

Asdre, Katerina ;

Nikolopoulos, Stavros D. ;

Papadopoulos, Charis .

JOURNAL OF PARALLEL AND DISTRIBUTED COMPUTING, 2007, 67 (01) :63-76

[4]

Boliac R, 2004, ARS COMBINATORIA, V72, P241

[5] On the vertex k-path cover [J].

Bresar, Bostjan ;

Jakovac, Marko ;

Katrenic, Jan ;

Semanisin, Gabriel ;

Taranenko, Andrej .

DISCRETE APPLIED MATHEMATICS, 2013, 161 (13-14) :1943-1949

[6] Minimum k-path vertex cover [J].

Bresar, Bostjan ;

Kardos, Frantisek ;

Katrenic, Jan ;

Semanisin, Gabriel .

DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) :1189-1195

[7] Independent packings in structured graphs [J].

Cameron, K ;

Hell, P .

MATHEMATICAL PROGRAMMING, 2006, 105 (2-3) :201-213

[8]

Chang M-S., 2014, 31 WORKSHOP COMBINAT, P9

[9] Fixed-parameter algorithms for vertex cover P3 [J].

Chang, Maw-Shang ;

Chen, Li-Hsuan ;

Hung, Ling-Ju ;

Rossmanith, Peter ;

Su, Ping-Chen .

DISCRETE OPTIMIZATION, 2016, 19 :12-22

[10] A generalization of Nemhauser and Trotter's local optimization theorem [J].

Fellows, Michael R. ;

Guo, Jiong ;

Moser, Hannes ;

Niedermeier, Rolf .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2011, 77 (06) :1141-1158

← 1 2 3 →