Standard
Parameterized complexity of superstring problems. / Bliznets, Ivan; Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.; Saurabh, Saket.
Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings. ред. / Ugo Vaccaro; Ely Porat; Ferdinando Cicalese. Springer Nature, 2015. стр. 89-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9133).
Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Harvard
Bliznets, I, Fomin, FV, Golovach, PA, Karpov, N
, Kulikov, AS & Saurabh, S 2015,
Parameterized complexity of superstring problems. в U Vaccaro, E Porat & F Cicalese (ред.),
Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 9133, Springer Nature, стр. 89-99, 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015, Ischia Island, Италия,
29/06/15.
https://doi.org/10.1007/978-3-319-19929-0_8
APA
Bliznets, I., Fomin, F. V., Golovach, P. A., Karpov, N.
, Kulikov, A. S., & Saurabh, S. (2015).
Parameterized complexity of superstring problems. в U. Vaccaro, E. Porat, & F. Cicalese (Ред.),
Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings (стр. 89-99). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9133). Springer Nature.
https://doi.org/10.1007/978-3-319-19929-0_8
Vancouver
Bliznets I, Fomin FV, Golovach PA, Karpov N
, Kulikov AS, Saurabh S.
Parameterized complexity of superstring problems. в Vaccaro U, Porat E, Cicalese F, Редакторы, Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings. Springer Nature. 2015. стр. 89-99. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
https://doi.org/10.1007/978-3-319-19929-0_8
Author
Bliznets, Ivan ; Fomin, Fedor V. ; Golovach, Petr A. ; Karpov, Nikolay
; Kulikov, Alexander S. ; Saurabh, Saket. /
Parameterized complexity of superstring problems. Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings. Редактор / Ugo Vaccaro ; Ely Porat ; Ferdinando Cicalese. Springer Nature, 2015. стр. 89-99 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{6ccf9eab676448ad8c9df5e29c1a24a7,
title = "Parameterized complexity of superstring problems",
abstract = "In the Shortest Superstring problem we are given a set of strings S = {s1,..., sn} and an integer ℓ and the question is to decide whether there is a superstring s of length at most ℓ containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2O(k) poly(n) finds a superstring of length at most ℓ containing at least k strings of S. We complement this by the lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.",
author = "Ivan Bliznets and Fomin, {Fedor V.} and Golovach, {Petr A.} and Nikolay Karpov and Kulikov, {Alexander S.} and Saket Saurabh",
year = "2015",
month = jan,
day = "1",
doi = "10.1007/978-3-319-19929-0_8",
language = "English",
isbn = "9783319199283",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "89--99",
editor = "Ugo Vaccaro and Ely Porat and Ferdinando Cicalese",
booktitle = "Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings",
address = "Germany",
note = "26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015 ; Conference date: 29-06-2015 Through 01-07-2015",
}
RIS
TY - GEN
T1 - Parameterized complexity of superstring problems
AU - Bliznets, Ivan
AU - Fomin, Fedor V.
AU - Golovach, Petr A.
AU - Karpov, Nikolay
AU - Kulikov, Alexander S.
AU - Saurabh, Saket
PY - 2015/1/1
Y1 - 2015/1/1
N2 - In the Shortest Superstring problem we are given a set of strings S = {s1,..., sn} and an integer ℓ and the question is to decide whether there is a superstring s of length at most ℓ containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2O(k) poly(n) finds a superstring of length at most ℓ containing at least k strings of S. We complement this by the lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.
AB - In the Shortest Superstring problem we are given a set of strings S = {s1,..., sn} and an integer ℓ and the question is to decide whether there is a superstring s of length at most ℓ containing all strings of S as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time 2O(k) poly(n) finds a superstring of length at most ℓ containing at least k strings of S. We complement this by the lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.
UR - http://www.scopus.com/inward/record.url?scp=84949058313&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-19929-0_8
DO - 10.1007/978-3-319-19929-0_8
M3 - Conference contribution
AN - SCOPUS:84949058313
SN - 9783319199283
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 89
EP - 99
BT - Combinatorial Pattern Matching - 26th Annual Symposium, CPM 2015, Proceedings
A2 - Vaccaro, Ugo
A2 - Porat, Ely
A2 - Cicalese, Ferdinando
PB - Springer Nature
T2 - 26th Annual Symposium on Combinatorial Pattern Matching, CPM 2015
Y2 - 29 June 2015 through 1 July 2015
ER -
