Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Complexity of algorithms on compressed data

2014/13/B/ST6/00770

Keywords:

algorithms complexity compression texts graphs networks

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory
  • ST1_14: Discrete mathematics and combinatorics
  • ST6_4: Formal methods, foundations of computer science, including theoretical computer science, quantum algorithms

Panel:

ST6 - Computer science and informatics: informatics and information systems, computer science, scientific computing, intelligent systems

Host institution :

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Other projects carried out by the institution 

Principal investigator (from the host institution):

prof. Wojciech Rytter 

Number of co-investigators in the project: 10

Call: OPUS 7 - announced on 2014-03-17

Amount awarded: 641 154 PLN

Project start date (Y-m-d): 2015-02-06

Project end date (Y-m-d): 2019-01-05

Project duration:: 47 months (the same as in the proposal)

Project status: Project settled

Equipment purchased [PL]

  1. trzy laptopy (2 618 PLN)

Information in the final report

  • Publication in academic press/journals (11)
  • Articles in post-conference publications (20)
  1. Covering problems for partial words and for indeterminate strings
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    TCS (rok: 2017, tom: 698, strony: 25-39), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2017.05.026 - link to the publication
  2. Order-preserving indexing
    Authors:
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Marcin Kubica, Alessio Langiu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    TCS (rok: 2016, tom: 638, strony: 122-135), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2015.06.050 - link to the publication
  3. String Powers in Trees. Algorithmica 79(3): 814-834
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    Algorithmica (rok: 2017, tom: 79, strony: 814-835), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-016-0271-3 - link to the publication
  4. On semi-perfect de Bruijn words.
    Authors:
    Damian Repke, Wojciech Rytter
    Academic press:
    Theor. Comput. Sci. (rok: 2018, tom: 720, strony: 55-63), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.02.008 - link to the publication
  5. Finding all solutions of equations in free groups and monoids with involution
    Authors:
    Volker Diekert, Artur Jez, Wojciech Plandowski
    Academic press:
    Information and Computation (rok: 2016, tom: 251, strony: 263-286), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2016.09.009 - link to the publication
  6. Maximum number of distinct and nonequivalent nonstandard squares in a word
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    TCS (rok: 2016, tom: 648, strony: 84–95), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.08.010 - link to the publication
  7. Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet.
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter
    Academic press:
    Algorithmica (rok: 2017, tom: 77, strony: 1194-1215), Wydawca: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-016-0140-0 - link to the publication
  8. Fast algorithms for Abelian periods in words and greatest common divisor queries.
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter
    Academic press:
    Journal of Computer and System Sciences (rok: 2017, tom: 84, strony: 205-218), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2016.09.003 - link to the publication
  9. On the greedy algorithm for the Shortest Common Superstring problem with reversals
    Authors:
    Gabriele Fici, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    IPL (rok: 2016, tom: 116(3), strony: 245-251), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2015.11.015 - link to the publication
  10. Two fast constructions of compact representations of binary words with given set of periods
    Authors:
    Wojciech Rytter
    Academic press:
    TCS (rok: 2016, tom: 656, strony: 180-187), Wydawca: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.04.027 - link to the publication
  11. Efficient Ranking of Lyndon Words and Decoding Lexicographically Minimal de Bruijn Sequence
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter
    Academic press:
    SIAM J. Discrete Math. (rok: 2016, tom: 30(4), strony: 2027-2046), Wydawca: SIAM
    Status:
    Published
    DOI:
    10.1137/15M1043248 - link to the publication
  1. Universal Reconstruction of a String.
    Authors:
    Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    WADS 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 28 Lipca
    Status:
    Published
    DOI:
    link to the publication
  2. Evacuation from a Disc in the Presence of a Faulty Robot
    Authors:
    Jurek CzyzowiczKonstantinos GeorgiouMaxime Godon Evangelos Kranakis Danny Krizanc Wojciech Rytter Michał Włodarczyk
    Conference:
    SIROCCO 2017 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja Czerwiec 19-22
    Status:
    Published
  3. Faster Longest Common Extension Queries in Strings over General Alphabets
    Authors:
    Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen
    Conference:
    CPM 2016 (rok: 2016, ), Wydawca: DROPS
    Data:
    konferencja 27-29 Czerwca
    Status:
    Published
    DOI:
    link to the publication
  4. Faster Recovery of Approximate Periods over Edit Distance
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
    Conference:
    SPIRE (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja Pażdziernik 9-11
    Status:
    Published
  5. A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques.
    Authors:
    Andrzej Lingas Mirosław Kowaluk
    Conference:
    WALCOM2017 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja Marzec 29–31
    Status:
    Published
  6. Broadcast with Energy-Exchanging Mobile Agents Distributed on a Tree
    Authors:
    Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
    Conference:
    SIROCCO (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja Czerwiec 18-21
    Status:
    Published
  7. Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries
    Authors:
    Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Ritu Kundu, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    SPIRE (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 18-20 Października
    Status:
    Published
    DOI:
    link to the publication
  8. On Periodicity Lemma for Partial Words
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    LATA (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja Kiwiecien 9-11
    Status:
    Published
  9. String Periods in the Order-Preserving Model
    Authors:
    Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny M. Shur, Tomasz Walen
    Conference:
    STACS (rok: 2018, ), Wydawca: Dagstuhl Research online Publications
    Data:
    konferencja Luty 28 - Marzec 3
    Status:
    Published
    DOI:
    link to the publication
  10. Tight Bound for the Number of Distinct Palindromes in a Tree.
    Authors:
    Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen:
    Conference:
    SPIRE 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 1 Września
    Status:
    Published
    DOI:
    link to the publication
  11. (1 + epsilon)-Approximate Incremental Matching in Constant Deterministic Amortized Time
    Authors:
    Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, Shay Solomon
    Conference:
    SODA (rok: 2019, ), Wydawca: ACM
    Data:
    konferencja Styczeń 6-9
    Status:
    Published
  12. Communication Problems for Mobile Agents Exchanging Energy
    Authors:
    Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
    Conference:
    SIROCCO (rok: 2016, ), Wydawca: Springer
    Data:
    konferencja 19-21 Lipca
    Status:
    Published
  13. Efficient Algorithms for Longest Closed Factor Array.
    Authors:
    Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto, Tomasz Walen
    Conference:
    SPIRE 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 1 Wrzesień
    Status:
    Published
    DOI:
    link to the publication
  14. Linear-Time Algorithm for Long {LCF} with k Mismatches
    Authors:
    Panagiotis Charalampopoulos , Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    CPM (rok: 2018, ), Wydawca: Springer
    Data:
    konferencja Lipiec 2-4
    Status:
    Published
  15. Towards minimal algorithms for big data analytics with spreadsheets
    Authors:
    Jacek Sroka, Lesniewski, Miroslaw Kowaluk, Krzysztof Stencel, Jerzy Tyszkiewicz
    Conference:
    ACM SIGMOD Workshop (rok: 2017, ), Wydawca: ACM
    Data:
    konferencja Maj 19
    Status:
    Published
  16. Efficient Enumeration of Non-Equivalent Squares in Partial Words with Few Holes.
    Authors:
    Panagiotis Charalampopoulos, Maxime Crochemore, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    COCOON 2017 (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja Sierpień 3-5
    Status:
    Published
  17. Efficient Representation and Counting of Antipower Fragments in Words
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyn ́ski, Tomasz Walen ́, and Wiktor Zuba
    Conference:
    LATA 2019 (rok: 2019, ), Wydawca: arxive
    Data:
    konferencja Marzec
    Status:
    Accepted for publication
  18. String Powers in Trees.
    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    CPM 2015 (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja 16 Czerwiec
    Status:
    Published
    DOI:
    link to the publication
  19. Energy-Optimal Broadcast in a Tree with Mobile Agents
    Authors:
    Jerzy Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
    Conference:
    Algosensors (rok: 2017, ), Wydawca: Springer
    Data:
    konferencja Wrzesień 7-8
    Status:
    Published
  20. Optimal Dynamic Strings
    Authors:
    Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, Piotr Sankowski:
    Conference:
    SODA (rok: 2018, ), Wydawca: ACM
    Data:
    konferencja Styczeń 2018
    Status:
    Published

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy