Prague Stringology Conference 2023
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 G1 = (V1, E1) and G2 = (V2, E2) that includes some string in the constraint labeled graph G3 = (V3, E3) as its subsequence. Firstly, we consider the case where G1, G2 and G3 are all acyclic, and present algorithms for computing their SEQ-IC-LCS in O(|E1||E2||E3|) time and O(|V1||V2||V3|) space. Secondly, we consider the case where G1 and G2 can be cyclic and G3 is acyclic, and present algorithms for computing their SEQ-IC-LCS in O(|E1||E2||E3| + |V1||V2||V3| log|Σ|) time and O(|V1||V2||V3) space, where Σ is the alphabet. |
| Download paper: |  |
 |
|
| BibTeX reference |