The Structure of Forward, Reverse, and Transverse Path Graphs in the Pattern Recognition Algorithms of Sellers.
Lewis Lasser, Louis A. D'Alotto · 2006
Abstract — In [3], [4], [5] Sellers developes a dynamic programming pattern matching algorithm that generates forward, reverse, and transverse path graphs that de-termine the best resemblance (lowest cost) of a smaller string pattern inside a larger. In this paper we study the properties and structure of these graphs. We show that these path graphs can be decomposed into a small number of distinct block types, that are used to analyze graph structure. It is also shown that an exact pattern match results in a disconnected transverse path graph.