Directed graph pattern matching and topological embedding

Pattern matching in directed graphs is a natural extension of pattern matching in trees and has many applications to different areas. In this paper, we study several pattern matching problems in ordered labeled directed graphs. For the rooted directed graph pattern matching problem, we present an efficient algorithm which, given a pattern graph P and a target graph T, runs in time and space O(\E(P)\ \V-T\ + \E(T)\). It is faster than the best known method by a factor of min{\E(T)\, \E(P)\ \V-T\}. This algorithm can also solve the directed graph pattern matching problem without increasing time or space complexity. Our solution to this problem outperforms the best existing method by Katzenelson, Pinter and Schenfeld by a factor of min{\V-P\ \E(T)\, \V-P\ \E(P)\ \V-T\}. We also present an algorithm for the directed graph topological embedding problem which runs in time O(\V-P\ \E(T)\ + \E(P)\) and space O(\V-P\ \V-T\ + \E(P)\ + \E(T)\). To our knowledge, this algorithm is the first one for this problem. (C) 1997 Academic Press.