Approximation Algorithms for Intersection Graphs

被引：0

作者：

Kammer, Frank ^{[1
]}

Tholey, Torsten ^{[1
]}

Voepel, Heiko ^{[1
]}

机构：

[1] Univ Augsburg, Inst Informat, D-86135 Augsburg, Germany

来源：

APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES | 2010年 / 6302卷

关键词：

UNIT DISK GRAPHS; GEOMETRIC GRAPHS; SCHEMES; PACKING; CLIQUE; PLANE; SETS;

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We study three complexity parameters that in some sense measure how chordal-like a graph is. The similarity to chordal graphs is used to construct simple polynomial-time approximation algorithms with constant approximation ratio for many NP-hard problems, when restricted to graphs for which at least one of the three complexity parameters is bounded by a constant. As applications we present approximation algorithms with constant approximation ratio for maximum weighted independent set; minimum (independent) dominating set, minimum vertex coloring, maximum weighted clique, and minimum clique partition for large classes of intersection graphs.

引用

页码：260 / 273

页数：14

共 34 条

[1] [Anonymous], 2002, APPL OPTIMIZAT
[2] Scheduling split intervals
Bar-Yehuda, R.
Halldorsson, M. M.
Naor, J.
Shachnai, H.
Shapira, I.
[J]. SIAM JOURNAL ON COMPUTING, 2006, 36 (01) : 1 - 15
[3] A linear-time ie algorithm for finding three-decompositions of small treewidth
Bodlaender, HL
[J]. SIAM JOURNAL ON COMPUTING, 1996, 25 (06) : 1305 - 1317
[4] Butman A, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P268
[5] CAREY MR, 1976, THEORETICAL COMPUTER, V1, P237
[6] Cerioli M.R., 2004, ELECT NOTES DISCRETE, V18, P73
[7] Polynomial-time approximation schemes for packing and piercing fat objects
Chan, TM
[J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2003, 46 (02): : 178 - 189
[8] UNIT DISK GRAPHS
CLARK, BN
COLBOURN, CJ
JOHNSON, DS
[J]. DISCRETE MATHEMATICS, 1990, 86 (1-3) : 165 - 177
[9] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS
COURCELLE, B
[J]. INFORMATION AND COMPUTATION, 1990, 85 (01) : 12 - 75
[10] DUMITRESCU A, ARXIV09091552V1

← 1 2 3 4 →