Anzeige
Erschienen in:
2012 | OriginalPaper | Buchkapitel
Optimization Problems in Dotted Interval Graphs
verfasst von : Danny Hermelin, Julián Mestre, Dror Rawitz
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The class of
D-dotted interval
(
D
-DI) graphs is the class of intersection graphs of arithmetic progressions with jump (common difference) at most
D
. We consider various classical graph-theoretic optimization problems in
D
-DI graphs of arbitrarily, but fixed,
D
.
We show that
Maximum Independent Set
,
Minimum Vertex Cover
, and
Minimum Dominating Set
can be solved in polynomial time in this graph class, answering an open question posed by Jiang
(Inf. Processing Letters, 98(1):29–33, 2006)
. We also show that
Minimum Vertex Cover
can be approximated within a factor of (1 +
ε
) for any
ε
> 0 in linear time. This algorithm generalizes to a wide class of deletion problems including the classical
Minimum Feedback Vertex Set
and
Minimum Planar Deletion
problems.
Our algorithms are based on classical results in algorithmic graph theory and new structural properties of
D
-DI graphs that may be of independent interest.