SucheApproximation algorithms for intersection graphs
Frank Kammer, Torsten Tholey, Heiko Voepel
2009-06
in: Universität Augsburg
Technical Report, Institute of Computer Science, University of Augsburg, May 2009
We introduce three new 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 our new 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.
Downloads:
- Approximation algorithms for intersection graphs - (tp2009-06.pdf, 760 KB)