Yuki Yonemoto, Yuto Nakashima and Shunsuke Inenaga
Computing SEQ-IC-LCS of Labeled Graphs
Abstract: |
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. |
Download paper: | |||
BibTeX reference |