Computing SEQ-IC-LCS of Labeled Graphs
share
We consider labeled directed graphs where each vertex is labeled with a non-empty string. Such labeled graphs are also known as non-linear texts in the literature. In this paper, we introduce a new problem of comparing two given labeled graphs, called the SEQ-IC-LCS problem on labeled graphs. The goal of SEQ-IC-LCS is to compute the the length of the longest common subsequence (LCS) Z of two target labeled graphs G_1 = (V_1, E_1) and G_2 = (V_2, E_2) that includes some string in the constraint labeled graph G_3 = (V_3, E_3) as its subsequence. Firstly, we consider the case where G_1, G_2 and G_3 are all acyclic, and present algorithms for computing their SEQ-IC-LCS in O(|E_1||E_2||E_3|) time and O(|V_1||V_2||V_3|) space. Secondly, we consider the case where G_1 and G_2 can be cyclic and G_3 is acyclic, and present algorithms for computing their SEQ-IC-LCS in O(|E_1||E_2||E_3| + |V_1||V_2||V_3|log|Σ|) time and O(|V_1||V_2||V_3|) space, where Σ is the alphabet.
READ FULL TEXT