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 graphPand a target graphT, runs in time and spaceO(|E_P| |V_T| + |E_T|). It is faster than the best known method by a factor ofmin{|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 ofmin{|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 timeO(|V_P| |E_T| + |E_P|) and spaceO(|V_P| |V_T| + |E_P| + |E_T|). To our knowledge, this algorithm is the first one for this problem.