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

Main titleBypass strong V-structures and find an isomorphic labelled subgraph in linear time
AuthorDörr, Heiko
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages12 S.
Series Freie Universität Berlin, Fachbereich Mathematik : Ser. B ; 94,8
Classification (DDC)004 Data processing and Computer science
AbstractThis 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.
Documents
pdf-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1994
Type of documentMaps
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2009-05-12 : 01:26:16
Last changed2014-01-23 : 04:21:25
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001863
Statistics
 

LOADING...