Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Graph Editing to a Fixed Target
verfasst von : Petr A. Golovach, Daniël Paulusma, Iain Stewart
Erschienen in: Combinatorial Algorithms
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
For a fixed graph
H
, the
H
-
Minor Edit
problem takes as input a graph
G
and an integer
k
and asks whether
G
can be modified into
H
by a total of at most
k
edge contractions, edge deletions and vertex deletions. Replacing edge contractions by vertex dissolutions yields the
H
-
Topological Minor Edit
problem. For each problem we show polynomial-time solvable and
NP
-complete cases depending on the choice of
H
. Moreover, when
G
is AT-free, chordal or planar, we show that
H
-
Minor Edit
is polynomial-time solvable for all graphs
H
.