Hardness results and approximation algorithms of k-tuple domination in graphs

被引：54

作者：

Klasing, R

Laforest, C

机构：

[1] Univ Evry, LaMI, F-91000 Evry, France

[2] Univ Nice, INRIA, CNRS, MASCOTTE Project, F-06902 Sophia Antipolis, France

来源：

INFORMATION PROCESSING LETTERS | 2004年 / 89卷 / 02期

关键词：

approximation algorithms; combinatorial problems; domination problems;

D O I：

10.1016/j.ipl.2003.10.004

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

The study of k-tuple domination problem in special graphs was presented. The complexity of the domination problem was analyzed by using the hardness results and approximation algorithms. In this regard, a linear-time algorithm for the 2-tuple domination problem in trees and in strongly chordal graphs was devised. The obtained approximation algorithm was a polynomial time algorithm whose output solution was compared with the optimal solution.

引用

页码：75 / 83

页数：9

共 8 条

[1] Some APX-completeness results for cubic graphs [J].

Alimonti, P ;

Kann, V .

THEORETICAL COMPUTER SCIENCE, 2000, 237 (1-2) :123-134

[2]

Chang G. J., 1998, HDB COMBINATORIAL OP, V3, P339

[3] A threshold of in n for approximating set cover [J].

Feige, U .

JOURNAL OF THE ACM, 1998, 45 (04) :634-652

[4]

Harary F, 2000, ARS COMBINATORIA, V55, P201

[5]

Liao CS, 2002, TAIWAN J MATH, V6, P415

[6] k-tuple domination in graphs [J].

Liao, CS ;

Chang, GJ .

INFORMATION PROCESSING LETTERS, 2003, 87 (01) :45-50

[7] SIMPLE HEURISTICS FOR UNIT DISK GRAPHS [J].

MARATHE, MV ;

BREU, H ;

HUNT, HB ;

RAVI, SS ;

ROSENKRANTZ, DJ .

NETWORKS, 1995, 25 (02) :59-68

[8]

[No title captured]

← 1 →