title: A new graph model and algorithms for consistent superstring problems.
abstract: Problems related to string inclusion and non-inclusion have been vigorously studied in diverse fields such as data compression, molecular biology and computer security. Given a finite set of positive strings P and a finite set of negative strings N, a string α is a consistent superstring if every positive string is a substring of α and no negative string is a substring of α. The shortest (resp. longest) consistent superstring problem is to find a string α that is the shortest (resp. longest) among all the consistent superstrings for the given sets of strings. In this paper, we first propose a new graph model for consistent superstrings for given P and N. In our graph model, the set of strings represented by paths satisfying some conditions is the same as the set of consistent superstrings for P and N. We also present algorithms for the shortest and the longest consistent superstring problems. Our algorithms solve the consistent superstring problems for all cases, including cases that are not considered in previous work. Moreover, our algorithms solve in polynomial time the consistent superstring problems for more cases than the previous algorithms. For the polynomially solvable cases, our algorithms are more efficient than the previous ones.
authors.affiliation: Department of Computer Science and Engineering, Sejong University, , Seoul 143-747, South Korea.
authors.forename: Joong Chae
authors.initials: JC
authors.lastname: Na
authors.forename: Sukhyeun
authors.initials: S
authors.lastname: Cho
authors.forename: Siwon
authors.initials: S
authors.lastname: Choi
authors.forename: Jin Wook
authors.initials: JW
authors.lastname: Kim
authors.forename: Kunsoo
authors.initials: K
authors.lastname: Park
authors.forename: Jeong Seop
authors.initials: JS
authors.lastname: Sim
mesh_terms: D000465:Algorithms; D003196:Computer Graphics; D008962:Models, Theoretical
keywords: consistent superstring; string inclusion; string non-inclusion