Zeira, Ron; Shamir, Ron Sorting by cuts, joins and whole chromosome duplications. (English) Zbl 1435.92041 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 396-409 (2015). MSC: 92D10 92-08 PDFBibTeX XMLCite \textit{R. Zeira} and \textit{R. Shamir}, Lect. Notes Comput. Sci. 9133, 396--409 (2015; Zbl 1435.92041) Full Text: DOI
Nicholson, Patrick K.; Raman, Rajeev Encoding nearest larger values. (English) Zbl 1432.68100 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 385-395 (2015). MSC: 68P05 PDFBibTeX XMLCite \textit{P. K. Nicholson} and \textit{R. Raman}, Lect. Notes Comput. Sci. 9133, 385--395 (2015; Zbl 1432.68100) Full Text: DOI Link
Nicaud, Cyril A probabilistic analysis of the reduction ratio in the suffix-array IS-algorithm. (English) Zbl 1432.68609 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 374-384 (2015). MSC: 68W32 68P05 68W40 PDFBibTeX XMLCite \textit{C. Nicaud}, Lect. Notes Comput. Sci. 9133, 374--384 (2015; Zbl 1432.68609) Full Text: DOI Link
Navarro, Gonzalo; Thankachan, Sharma V. Reporting consecutive substring occurrences under bounded gap constraints. (English) Zbl 1432.68099 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 367-373 (2015). MSC: 68P05 PDFBibTeX XMLCite \textit{G. Navarro} and \textit{S. V. Thankachan}, Lect. Notes Comput. Sci. 9133, 367--373 (2015; Zbl 1432.68099) Full Text: DOI
Matsuoka, Yoshiaki; I, Tomohiro; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki Semi-dynamic compact index for short patterns and succinct van Emde Boas tree. (English) Zbl 1432.68097 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 355-366 (2015). MSC: 68P05 68P15 68W32 PDFBibTeX XMLCite \textit{Y. Matsuoka} et al., Lect. Notes Comput. Sci. 9133, 355--366 (2015; Zbl 1432.68097) Full Text: DOI
Loptev, Alexander; Kucherov, Gregory; Starikovskaya, Tatiana On maximal unbordered factors. (English) Zbl 1397.68150 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 343-354 (2015). MSC: 68R15 68W32 PDFBibTeX XMLCite \textit{A. Loptev} et al., Lect. Notes Comput. Sci. 9133, 343--354 (2015; Zbl 1397.68150) Full Text: DOI arXiv
Kärkkäinen, Juha; Kempa, Dominik; Puglisi, Simon J. Parallel external memory suffix sorting. (English) Zbl 1432.68110 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 329-342 (2015). MSC: 68P10 68W10 68W32 PDFBibTeX XMLCite \textit{J. Kärkkäinen} et al., Lect. Notes Comput. Sci. 9133, 329--342 (2015; Zbl 1432.68110) Full Text: DOI
Kärkkäinen, Juha; Kempa, Dominik; Piątkowski, Marcin Tighter bounds for the sum of irreducible LCP values. (English) Zbl 1356.68056 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 316-328 (2015). MSC: 68P20 68P30 68R15 PDFBibTeX XMLCite \textit{J. Kärkkäinen} et al., Lect. Notes Comput. Sci. 9133, 316--328 (2015; Zbl 1356.68056) Full Text: DOI
Kulikov, Alexander S.; Savinov, Sergey; Sluzhaev, Evgeniy Greedy conjecture for strings of length 4. (English) Zbl 1432.68607 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 307-315 (2015). MSC: 68W32 68W25 PDFBibTeX XMLCite \textit{A. S. Kulikov} et al., Lect. Notes Comput. Sci. 9133, 307--315 (2015; Zbl 1432.68607) Full Text: DOI
Kosolobov, Dmitry Online detection of repetitions with backtracking. (English) Zbl 1432.68591 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 295-306 (2015). MSC: 68W27 68W32 68W40 PDFBibTeX XMLCite \textit{D. Kosolobov}, Lect. Notes Comput. Sci. 9133, 295--306 (2015; Zbl 1432.68591) Full Text: DOI arXiv
Kociumaka, Tomasz; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz String powers in trees. (English) Zbl 1380.68322 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 284-294 (2015). MSC: 68R15 PDFBibTeX XMLCite \textit{T. Kociumaka} et al., Lect. Notes Comput. Sci. 9133, 284--294 (2015; Zbl 1380.68322) Full Text: DOI
Jansson, Jesper; Lingas, Andrzej; Lundell, Eva-Marta The approximability of maximum rooted triplets consistency with fan triplets and forbidden triplets. (English) Zbl 1432.68577 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 272-283 (2015). MSC: 68W25 92D15 PDFBibTeX XMLCite \textit{J. Jansson} et al., Lect. Notes Comput. Sci. 9133, 272--283 (2015; Zbl 1432.68577) Full Text: DOI
Istrate, Gabriel; Bonchiş, Cosmin Partition into heapable sequences, heap tableaux and a multiset extension of Hammersley’s process. (English) Zbl 1432.68326 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 261-271 (2015). MSC: 68R05 05A05 60K35 68P10 68W32 PDFBibTeX XMLCite \textit{G. Istrate} and \textit{C. Bonchiş}, Lect. Notes Comput. Sci. 9133, 261--271 (2015; Zbl 1432.68326) Full Text: DOI arXiv
Hon, Wing-Kai; Lam, Tak-Wah; Shah, Rahul; Thankachan, Sharma V.; Ting, Hing-Fung; Yang, Yilin Dictionary matching with uneven gaps. (English) Zbl 1383.68105 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 247-260 (2015). MSC: 68W32 68P05 PDFBibTeX XMLCite \textit{W.-K. Hon} et al., Lect. Notes Comput. Sci. 9133, 247--260 (2015; Zbl 1383.68105) Full Text: DOI
Haleš, Jozef; Maňuch, Ján; Ponty, Yann; Stacho, Ladislav Combinatorial RNA design: designability and structure-approximating algorithm. (English) Zbl 1432.68374 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 231-246 (2015). MSC: 68R15 68W25 68W32 92D20 PDFBibTeX XMLCite \textit{J. Haleš} et al., Lect. Notes Comput. Sci. 9133, 231--246 (2015; Zbl 1432.68374) Full Text: DOI arXiv
Goto, Keisuke; Bannai, Hideo; Inenaga, Shunsuke; Takeda, Masayuki LZD factorization: simple and practical online grammar compression with variable-to-fixed encoding. (English) Zbl 1432.68141 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 219-230 (2015). MSC: 68P30 68W32 PDFBibTeX XMLCite \textit{K. Goto} et al., Lect. Notes Comput. Sci. 9133, 219--230 (2015; Zbl 1432.68141) Full Text: DOI
Gog, Simon; Petri, Matthias Compact indexes for flexible top-\(k\). (English) Zbl 1432.68121 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 207-218 (2015). MSC: 68P20 68P15 PDFBibTeX XMLCite \textit{S. Gog} and \textit{M. Petri}, Lect. Notes Comput. Sci. 9133, 207--218 (2015; Zbl 1432.68121) Full Text: DOI arXiv
Gawrychowski, Paweł; Nicholson, Patrick K. Encodings of range maximum-sum segment queries and applications. (English) Zbl 1432.68090 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 196-206 (2015). MSC: 68P05 68P15 PDFBibTeX XMLCite \textit{P. Gawrychowski} and \textit{P. K. Nicholson}, Lect. Notes Comput. Sci. 9133, 196--206 (2015; Zbl 1432.68090) Full Text: DOI arXiv
Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V. Succinct non-overlapping indexing. (English) Zbl 1432.68089 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 185-195 (2015). MSC: 68P05 68P15 68W32 PDFBibTeX XMLCite \textit{A. Ganguly} et al., Lect. Notes Comput. Sci. 9133, 185--195 (2015; Zbl 1432.68089) Full Text: DOI
Fischer, Johannes; I, Tomohiro; Köppl, Dominik Lempel Ziv computation in small space (LZ-CISS). (English) Zbl 1432.68138 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 172-184 (2015). MSC: 68P30 68W32 PDFBibTeX XMLCite \textit{J. Fischer} et al., Lect. Notes Comput. Sci. 9133, 172--184 (2015; Zbl 1432.68138) Full Text: DOI arXiv
Fischer, Johannes; Gawrychowski, Paweł Alphabet-dependent string searching with wexponential search trees. (English) Zbl 1432.68087 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 160-171 (2015). MSC: 68P05 68P10 68W32 PDFBibTeX XMLCite \textit{J. Fischer} and \textit{P. Gawrychowski}, Lect. Notes Comput. Sci. 9133, 160--171 (2015; Zbl 1432.68087) Full Text: DOI arXiv
Davoodi, Pooya; Iacono, John; Landau, Gad M.; Lewenstein, Moshe Range minimum query indexes in higher dimensions. (English) Zbl 1432.68086 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 149-159 (2015). MSC: 68P05 68P15 PDFBibTeX XMLCite \textit{P. Davoodi} et al., Lect. Notes Comput. Sci. 9133, 149--159 (2015; Zbl 1432.68086) Full Text: DOI
Cho, Sukhyeun; Na, Joong Chae; Sim, Jeong Seop Improved algorithms for the boxed-mesh permutation pattern matching problem. (English) Zbl 1380.68466 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 138-148 (2015). MSC: 68W32 68R05 68W40 PDFBibTeX XMLCite \textit{S. Cho} et al., Lect. Notes Comput. Sci. 9133, 138--148 (2015; Zbl 1380.68466) Full Text: DOI
Chikhi, Rayan; Medvedev, Paul; Milanič, Martin; Raskhodnikova, Sofya On the readability of overlap digraphs. (English) Zbl 1435.05090 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 124-137 (2015). MSC: 05C20 PDFBibTeX XMLCite \textit{R. Chikhi} et al., Lect. Notes Comput. Sci. 9133, 124--137 (2015; Zbl 1435.05090) Full Text: DOI arXiv
Chan, Timothy; Lewenstein, Moshe Fast string dictionary lookup with one error. (English) Zbl 1432.68084 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 114-123 (2015). MSC: 68P05 68P15 68W32 PDFBibTeX XMLCite \textit{T. Chan} and \textit{M. Lewenstein}, Lect. Notes Comput. Sci. 9133, 114--123 (2015; Zbl 1432.68084) Full Text: DOI
Bonizzoni, Paola; Dondi, Riccardo; Klau, Gunnar W.; Pirola, Yuri; Pisanti, Nadia; Zaccaria, Simone On the fixed parameter tractability and approximability of the minimum error correction problem. (English) Zbl 1432.68188 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 100-113 (2015). MSC: 68Q27 68W25 68W32 92D10 PDFBibTeX XMLCite \textit{P. Bonizzoni} et al., Lect. Notes Comput. Sci. 9133, 100--113 (2015; Zbl 1432.68188) Full Text: DOI Link
Bliznets, Ivan; Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.; Saurabh, Saket Parameterized complexity of superstring problems. (English) Zbl 1380.68216 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 89-99 (2015). MSC: 68Q25 68W32 PDFBibTeX XMLCite \textit{I. Bliznets} et al., Lect. Notes Comput. Sci. 9133, 89--99 (2015; Zbl 1380.68216) Full Text: DOI arXiv
Biswas, Sudip; Ganguly, Arnab; Shah, Rahul; Thankachan, Sharma V. Ranked document retrieval with forbidden pattern. (English) Zbl 1432.68120 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 77-88 (2015). MSC: 68P20 68W32 PDFBibTeX XMLCite \textit{S. Biswas} et al., Lect. Notes Comput. Sci. 9133, 77--88 (2015; Zbl 1432.68120) Full Text: DOI
Bille, Philip; Gørtz, Inge Li; Knudsen, Mathias Bæk Tejs; Lewenstein, Moshe; Vildhøj, Hjalte Wedel Longest common extensions in sublinear space. (English) Zbl 1380.68139 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 65-76 (2015). MSC: 68P05 68Q25 PDFBibTeX XMLCite \textit{P. Bille} et al., Lect. Notes Comput. Sci. 9133, 65--76 (2015; Zbl 1380.68139) Full Text: DOI arXiv
Bille, Philip; Gawrychowski, Paweł; Gørtz, Inge Li; Landau, Gad M.; Weimann, Oren Longest common extensions in trees. (English) Zbl 1432.68083 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 52-64 (2015). MSC: 68P05 68Q25 68W32 PDFBibTeX XMLCite \textit{P. Bille} et al., Lect. Notes Comput. Sci. 9133, 52--64 (2015; Zbl 1432.68083) Full Text: DOI arXiv
Beller, Timo; Ohlebusch, Enno Efficient construction of a compressed de Bruijn graph for pan-genome analysis. (English) Zbl 1432.68602 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 40-51 (2015). MSC: 68W32 68P30 68W40 92D10 92D20 PDFBibTeX XMLCite \textit{T. Beller} and \textit{E. Ohlebusch}, Lect. Notes Comput. Sci. 9133, 40--51 (2015; Zbl 1432.68602) Full Text: DOI
Belazzougui, Djamal; Cunial, Fabio; Gagie, Travis; Prezza, Nicola; Raffinot, Mathieu Composite repetition-aware data structures. (English) Zbl 1432.68082 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 26-39 (2015). MSC: 68P05 68W32 PDFBibTeX XMLCite \textit{D. Belazzougui} et al., Lect. Notes Comput. Sci. 9133, 26--39 (2015; Zbl 1432.68082) Full Text: DOI arXiv
Belazzougui, Djamal; Cunial, Fabio A framework for space-efficient string kernels. (English) Zbl 1380.68462 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19928-3/pbk; 978-3-319-19929-0/ebook). Lecture Notes in Computer Science 9133, 13-25 (2015). MSC: 68W32 68P05 68Q25 PDFBibTeX XMLCite \textit{D. Belazzougui} and \textit{F. Cunial}, Lect. Notes Comput. Sci. 9133, 13--25 (2015; Zbl 1380.68462) Full Text: DOI arXiv
Amir, Amihood; Porat, Benny On the hardness of optimal vertex relabeling and restricted vertex relabeling. (English) Zbl 1432.68331 Cicalese, Ferdinando (ed.) et al., Combinatorial pattern matching. 26th annual symposium, CPM 2015, Ischia Island, Italy, June 29 – July 1, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9133, 1-12 (2015). MSC: 68R10 68Q17 PDFBibTeX XMLCite \textit{A. Amir} and \textit{B. Porat}, Lect. Notes Comput. Sci. 9133, 1--12 (2015; Zbl 1432.68331) Full Text: DOI