2013 | OriginalPaper | Buchkapitel
Induced Subtrees in Interval Graphs
verfasst von : Pinar Heggernes, Pim van ’t Hof, Martin Milanič
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
The
Induced Subtree Isomorphism
problem takes as input a graph
G
and a tree
T
, and the task is to decide whether
G
has an induced subgraph that is isomorphic to
T
. This problem is known to be NP-complete on bipartite graphs, but it can be solved in polynomial time when
G
is a forest. We show that
Induced Subtree Isomorphism
can be solved in polynomial time when
G
is an interval graph. In contrast to this positive result, we show that the closely related
Subtree Isomorphism
problem is NP-complete even when
G
is restricted to the class of proper interval graphs, a well-known subclass of interval graphs.