Bypass Strong V-Structures and Find an Isomorphic
Labelled Subgraph in Linear Time
Heiko Dörr
Institut für Informatik
Freie Universität Berlin
email: doerr@inf.fu-berlin.de
Report B-94-08
7/13/94
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 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.
Get the report by anonymous ftp:
Server: fubinf.inf.fu-berlin.de
File: pub/reports/tr-b-94-08.ps.gz