2011 | OriginalPaper | Buchkapitel
Unique Small Subgraphs Are Not Easier to Find
verfasst von : Mirosław Kowaluk, Andrzej Lingas, Eva-Marta Lundell
Erschienen in: Language and Automata Theory and Applications
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
Given a pattern graph
H
of fixed size, and a host graph
G
guaranteed to contain at most one occurrence of a subgraph isomorphic to
H
, we show that both the problem of finding such an occurrence (if any) as well as the decision version of the problem are as hard as in the general case when
G
may contain several occurrences of
H
.