Zmiana języka

Projects search

Complexity of algorithms on compressed data

2014/13/B/ST6/00770

Keywords

Descriptors

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier
  • ST1_14: Kombinatoryka
  • ST6_4: Metody formalne, teoretyczne podstawy informatyki w tym informatyka teoretyczna

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

Voivodeship: 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
2015-02-06
Project end date
2019-01-05
Project duration
47 months (the same as in the proposal)
Project status
Project settled

Equipment purchased [PL]

  1. trzy laptopy. Cost: 2 618 PLN

Information in the final report

Publication in academic press/journals (11)

  1. 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 (year: 2016, volume: 116(3), pages: 245-251), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ipl.2015.11.015 – 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 (year: 2016, volume: 638, pages: 122-135), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2015.06.050 – link to the publication

  3. Finding all solutions of equations in free groups and monoids with involution

    Authors:
    Volker Diekert, Artur Jez, Wojciech Plandowski
    Academic press:
    Information and Computation (year: 2016, volume: 251, pages: 263-286), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.ic.2016.09.009 – link to the publication

  4. Two fast constructions of compact representations of binary words with given set of periods

    Authors:
    Wojciech Rytter
    Academic press:
    TCS (year: 2016, volume: 656, pages: 180-187), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.04.027 – link to the publication

  5. 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. (year: 2016, volume: 30(4), pages: 2027-2046), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/15M1043248 – 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 (year: 2016, volume: 648, pages: 84–95), Publisher: 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 (year: 2017, volume: 77, pages: 1194-1215), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-016-0140-0 – link to the publication

  8. On semi-perfect de Bruijn words.

    Authors:
    Damian Repke, Wojciech Rytter
    Academic press:
    Theor. Comput. Sci. (year: 2018, volume: 720, pages: 55-63), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2018.02.008 – link to the publication

  9. String Powers in Trees. Algorithmica 79(3): 814-834

    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    Algorithmica (year: 2017, volume: 79, pages: 814-835), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-016-0271-3 – link to the publication

  10. 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 (year: 2017, volume: 84, pages: 205-218), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.jcss.2016.09.003 – link to the publication

  11. Covering problems for partial words and for indeterminate strings

    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Academic press:
    TCS (year: 2017, volume: 698, pages: 25-39), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2017.05.026 – link to the publication

Articles in post-conference publications (20)

  1. String Powers in Trees.

    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    CPM 2015 (year: 2015, pages: 284-294), Publisher: Springer
    Date:
    conference 16 Czerwiec
    Status:
    Published
    DOI:
    link to the publication

  2. Communication Problems for Mobile Agents Exchanging Energy

    Authors:
    Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
    Conference:
    SIROCCO (year: 2016, pages: 275-288), Publisher: Springer
    Date:
    conference 19-21 Lipca
    Status:
    Published

  3. On Periodicity Lemma for Partial Words

    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    LATA (year: 2018, pages: 232-244), Publisher: Springer
    Date:
    conference Kiwiecien 9-11
    Status:
    Published

  4. Towards minimal algorithms for big data analytics with spreadsheets

    Authors:
    Jacek Sroka, Lesniewski, Miroslaw Kowaluk, Krzysztof Stencel, Jerzy Tyszkiewicz
    Conference:
    ACM SIGMOD Workshop (year: 2017, pages: 1:1--1:4), Publisher: ACM
    Date:
    conference Maj 19
    Status:
    Published

  5. Faster Longest Common Extension Queries in Strings over General Alphabets

    Authors:
    Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen
    Conference:
    CPM 2016 (year: 2016, pages: 5:1-5:13), Publisher: DROPS
    Date:
    conference 27-29 Czerwca
    Status:
    Published
    DOI:
    link to the publication

  6. 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 (year: 2015, pages: 95-102), Publisher: Springer
    Date:
    conference 1 Wrzesień
    Status:
    Published
    DOI:
    link to the publication

  7. Tight Bound for the Number of Distinct Palindromes in a Tree.

    Authors:
    Pawel Gawrychowski, Tomasz Kociumaka, Wojciech Rytter, Tomasz Walen:
    Conference:
    SPIRE 2015 (year: 2015, pages: 270-276), Publisher: Springer
    Date:
    conference 1 Września
    Status:
    Published
    DOI:
    link to the publication

  8. Universal Reconstruction of a String.

    Authors:
    Pawel Gawrychowski, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen
    Conference:
    WADS 2015 (year: 2015, pages: 386-397), Publisher: Springer
    Date:
    conference 28 Lipca
    Status:
    Published
    DOI:
    link to the publication

  9. 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 (year: 2016, pages: 22-34), Publisher: Springer
    Date:
    conference 18-20 Października
    Status:
    Published
    DOI:
    link to the publication

  10. A Fast Deterministic Detection of Small Pattern Graphs in Graphs Without Large Cliques.

    Authors:
    Andrzej Lingas Mirosław Kowaluk
    Conference:
    WALCOM2017 (year: 2017, pages: 217-227), Publisher: Springer
    Date:
    conference Marzec 29–31
    Status:
    Published

  11. 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 (year: 2017, pages: 158-173), Publisher: Springer
    Date:
    conference Czerwiec 19-22
    Status:
    Published

  12. String Periods in the Order-Preserving Model

    Authors:
    Garance Gourdel, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Arseny M. Shur, Tomasz Walen
    Conference:
    STACS (year: 2018, pages: 38:1-38:16), Publisher: Dagstuhl Research online Publications
    Date:
    conference Luty 28 - Marzec 3
    Status:
    Published
    DOI:
    link to the publication

  13. 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 (year: 2017, pages: 99-111), Publisher: Springer
    Date:
    conference Sierpień 3-5
    Status:
    Published

  14. Broadcast with Energy-Exchanging Mobile Agents Distributed on a Tree

    Authors:
    Jurek Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
    Conference:
    SIROCCO (year: 2018, pages: 209-2215), Publisher: Springer
    Date:
    conference Czerwiec 18-21
    Status:
    Published

  15. Faster Recovery of Approximate Periods over Edit Distance

    Authors:
    Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszynski, Tomasz Walen, Wiktor Zuba
    Conference:
    SPIRE (year: 2018, pages: 233-240), Publisher: Springer
    Date:
    conference Pażdziernik 9-11
    Status:
    Published

  16. Optimal Dynamic Strings

    Authors:
    Pawel Gawrychowski, Adam Karczmarz, Tomasz Kociumaka, Jakub Lacki, Piotr Sankowski:
    Conference:
    SODA (year: 2018, pages: 1509-1528), Publisher: ACM
    Date:
    conference Styczeń 2018
    Status:
    Published

  17. 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 (year: 2018, pages: 23:1--23:16), Publisher: Springer
    Date:
    conference Lipiec 2-4
    Status:
    Published

  18. (1 + epsilon)-Approximate Incremental Matching in Constant Deterministic Amortized Time

    Authors:
    Fabrizio Grandoni, Stefano Leonardi, Piotr Sankowski, Chris Schwiegelshohn, Shay Solomon
    Conference:
    SODA (year: 2019, pages: 1886--1898), Publisher: ACM
    Date:
    conference Styczeń 6-9
    Status:
    Published

  19. Energy-Optimal Broadcast in a Tree with Mobile Agents

    Authors:
    Jerzy Czyzowicz, Krzysztof Diks, Jean Moussi, Wojciech Rytter
    Conference:
    Algosensors (year: 2017, pages: 98-13), Publisher: Springer
    Date:
    conference Wrzesień 7-8
    Status:
    Published

  20. 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 (year: 2019, pages: 46035), Publisher: arxive
    Status:
    Accepted for publication

« New search

Graphic design and implementation: Jakub Piotrowski