Objekt-Metadaten

Bypass strong V-structures and find an isomorphic labelled subgraph in linear time
Dörr, Heiko ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

HaupttitelBypass strong V-structures and find an isomorphic labelled subgraph in linear time
AutorDörr, Heiko
Institution/KörperschaftUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
Seitenzahl12 S.
Schriftenreihe Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,8
DDC004 Datenverarbeitung; Informatik
ZusammenfassungThis 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 results 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 progress for any implementation
project.
Dokumente
pdf-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
 
Fachbereich/EinrichtungFB Mathematik und Informatik
Arbeitsbereich/InstitutInstitut für Informatik
Erscheinungsjahr1994
Dokumententyp/-SammlungenKarten
SpracheEnglisch
Rechte Nutzungsbedingungen
Erstellt am12.05.2009 - 13:26:16
Letzte Änderung23.01.2014 - 16:21:25
 
Statische URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001863
Zugriffsstatistik
 

LOADING...