Title: Marked subgraph isomorphism of ordered graphs
Abstract: Recently, the concept of ordered graphs has been introduced and it was shown that isomorphism of ordered graphs can be solved in quadratic time. In the present paper we consider a special case of the subgraph isomorphism problem for ordered graphs, called marked subgraph isomorphism. An algorithm of O(m 1 m 2) complexity is developed for finding all marked subgraph isomorphisms from a graph G 1 to another graph G 2, where m 1 and m 2 are the number of edges in G 1 and G 2, respectively. We demonstrate the usefulness of our algorithm by applying it to solving the subcircuit extraction problem. It turns out that our approach is much more efficient than traditional methods based on general subgraph isomorphism techniques.