
doi: 10.1007/bfb0033230
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(m1m2) complexity is developed for finding all marked subgraph isomorphisms from a graph G1 to another graph G2, where m1 and m2 are the number of edges in G1 and G2, 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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
