Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Algorytmika problemów o zwartej reprezentacji

2014/13/B/ST6/00770

Słowa kluczowe:

algorytmy złożoność kompresja teksty grafy sieci

Deskryptory:

  • 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 - Informatyka i technologie informacyjne: technologie i systemy informacyjne, informatyka, obliczenia naukowe, systemy inteligentne

Jednostka realizująca:

Uniwersytet Warszawski, Wydział Matematyki, Informatyki i Mechaniki

woj. mazowieckie

Inne projekty tej jednostki 

Kierownik projektu (z jednostki realizującej):

prof. Wojciech Rytter 

Liczba wykonawców projektu: 10

Konkurs: OPUS 7 - ogłoszony 2014-03-17

Przyznana kwota: 641 154 PLN

Rozpoczęcie projektu: 2015-02-01

Zakończenie projektu: 2019-01-05

Planowany czas trwania projektu: 47 miesięcy (z wniosku)

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. trzy laptopy. Za kwotę 2 618 PLN

Dane z raportu końcowego/rocznego

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

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy