Anzeige
Erschienen in:
1995 | ReviewPaper | Buchkapitel
Bypass strong V-structures and find an isomorphic labelled subgraph in linear time
verfasst von : Heiko Dörr
Erschienen in: Graph-Theoretic Concepts in Computer Science
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
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
This paper identifies a condition for which the existence of an isomorphic subgraph can be decided in linear time. The condition is evaluated in two steps. First the host graph is analysed to determine its strong V-structures. Then the guest graph must be appropriately represented. If this representation exists, the given algorithm constructively decides the subgraph isomorphism problem for the guest and the host graph in linear time.The result applies especially to the implementation of graph rewriting systems. An isomorphic subgraph must be determined automatically in each rewriting step. Thus the efficient solution presented in this paper is an important advancement for any implementation project.