String Matching in (Block) Graphs: A Full Classification by Walk Length

Sebastian Angrick, Ben Bals, Paweł Gawrychowski +2

We consider directed graphs in which the nodes are labeled with strings. A walk in such a graph naturally corresponds to the concatenation of the visited nodes' labels. These graph…