Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Solving 3-superstring in 3n/3 time. / Golovnev, Alexander; Kulikov, Alexander S.; Mihajlin, Ivan.
Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings. 2013. p. 480-491 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8087 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - Solving 3-superstring in 3n/3 time
AU - Golovnev, Alexander
AU - Kulikov, Alexander S.
AU - Mihajlin, Ivan
PY - 2013/10/15
Y1 - 2013/10/15
N2 - In the shortest common superstring problem (SCS) one is given a set s 1,..., sn of n strings and the goal is to find a shortest string containing each si as a substring. While many approximation algorithms for this problem have been developed, it is still not known whether it can be solved exactly in fewer than 2n steps. In this paper we present an algorithm that solves the special case when all of the input strings have length 3 in time 3n/3 and polynomial space. The algorithm generates a combination of a de Bruijn graph and an overlap graph, such that a SCS is then a shortest directed rural postman path (DRPP) on this graph. We show that there exists at least one optimal DRPP satisfying some natural properties. The algorithm works basically by exhaustive search, but on the reduced search space of such paths of size 3n/3.
AB - In the shortest common superstring problem (SCS) one is given a set s 1,..., sn of n strings and the goal is to find a shortest string containing each si as a substring. While many approximation algorithms for this problem have been developed, it is still not known whether it can be solved exactly in fewer than 2n steps. In this paper we present an algorithm that solves the special case when all of the input strings have length 3 in time 3n/3 and polynomial space. The algorithm generates a combination of a de Bruijn graph and an overlap graph, such that a SCS is then a shortest directed rural postman path (DRPP) on this graph. We show that there exists at least one optimal DRPP satisfying some natural properties. The algorithm works basically by exhaustive search, but on the reduced search space of such paths of size 3n/3.
UR - http://www.scopus.com/inward/record.url?scp=84885208919&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-40313-2_43
DO - 10.1007/978-3-642-40313-2_43
M3 - Conference contribution
AN - SCOPUS:84885208919
SN - 9783642403125
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 480
EP - 491
BT - Mathematical Foundations of Computer Science 2013 - 38th International Symposium, MFCS 2013, Proceedings
T2 - 38th International Symposium on Mathematical Foundations of Computer Science, MFCS 2013
Y2 - 26 August 2013 through 30 August 2013
ER -
ID: 49826082