Closest 4-leaf power is fixed-parameter tractable

被引：7

作者：

Dom, Michael ^{[1
]}

Guo, Jiong ^{[1
]}

Hueffner, Falk ^{[1
]}

Niedermeier, Rolf ^{[1
]}

机构：

[1] Univ Jena, Inst Informat, D-07743 Jena, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2008年 / 156卷 / 18期

关键词：

Fixed-parameter tractability; Graph algorithm; Graph modification; Graph power; Leaf power; Forbidden subgraph characterization;

D O I：

10.1016/j.dam.2008.01.007

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The NP-complete CLOSEST 4-LEAF POWER problem asks, given an undirected graph, whether it can be modified by at most r edge insertions or deletions such that it becomes a 4-leaf power. Herein, a 4-leaf power is a graph that can be constructed by considering an unrooted tree-the 4-leaf root-with leaves one-to-one labeled by the graph vertices, where we connect two graph vertices by an edge iff their corresponding leaves are at distance at most 4 in the tree. Complementing previous work on CLOSEST 2-LEAF POWER and CLOSEST 3-LEAF POWER, we give the first algorithmic result for CLOSEST 4-LEAF POWER, showing that CLOSEST 4-LEAF POWER is fixed-parameter tractable with respect to the parameter r. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：3345 / 3361

页数：17

共 37 条

[1]

AILON N, 2005, TR71905 PRINC U DEP

[2] Correlation clustering [J].