Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Proper Interval Vertex Deletion
verfasst von : Yngve Villanger
Erschienen in: Parameterized and Exact Computation
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
Deleting a minimum number of vertices from a graph to obtain a proper interval graph is an
NP
-complete problem. At
WG
2010
van Bevern et al.
gave an
O
((14
k
+ 14)
k
+ 1
kn
6
) time algorithm by combining iterative compression, branching, and a greedy algorithm. We show that there exists a simple greedy
O
(
n
+
m
) time algorithm that solves the
Proper Interval Vertex Deletion
problem on
$\{claw,net,\allowbreak tent,\allowbreak C_4,C_5,C_6\}$
-free graphs. Combining this with branching on the forbidden structures
$claw,net,tent,\allowbreak C_4,C_5,$
and
C
6
enables us to get an
O
(
kn
6
6
k
) time algorithm for
Proper Interval Vertex Deletion
, where
k
is the number of deleted vertices.