Fig. 9
From: Revisiting the complexity of and algorithms for the graph traversal edit distance and its variants
An example of a fractional optimal solution to the LP in (11)–(12) and the LP in (5)–(8). a A pair of input graphs to the LP in (11)–(12) and the LP in (5)–(8). The letters in red are edge labels. b A subgraph of \(\mathcal {A} (G_1, G_2)\) that is induced by alignment edges with non-zero weights (blue font) in an optimal solution to the LPs. The letters in red show the matching between the edge labels or between edge labels and gaps