Projekty finansowane przez NCN

Dane kierownika projektu i jednostki realizującej

Szczegółowe informacje o projekcie i konkursie

Słowa kluczowe

Aparatura

Wyczyść formularz

Aktualne trendy w algorytmach parametryzowanych i wykładniczych

2013/09/B/ST6/03136

Słowa kluczowe:

algorytmy złożoność parametryzowana kernelizacja algorytmy wykładnicze

Deskryptory:

  • ST6_6: Algorytmika, algorytmy równoległe, rozproszone i sieciowe, algorytmiczna teoria gier

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):

dr hab. Łukasz Kowalik 

Liczba wykonawców projektu: 5

Konkurs: OPUS 5 - ogłoszony 2013-03-15

Przyznana kwota: 603 180 PLN

Rozpoczęcie projektu: 2014-03-01

Zakończenie projektu: 2017-03-20

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

Status projektu: Projekt rozliczony

Zakupiona aparatura

  1. laptop.
  2. laptop ze stacją dokującą, klawiaturą i monitorem. Za kwotę 6 000 PLN
  3. komputer z monitorem. Za kwotę 4 000 PLN

Dane z raportu końcowego/rocznego

  • Publikacje w czasopismach (11)
  • Teksty w publikacjach pokonferencyjnych (14)
  1. A 13k-kernel for planar feedback vertex set via region decomposition
    Autorzy:
    Marthe Bonamy, Lukasz Kowalik
    Czasopismo:
    Theoretical Computer Science (rok: 2016, tom: 645, strony: 25-40), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2016.05.031 - link do publikacji
  2. Assigning Channels Via the Meet-in-the-Middle Approach
    Autorzy:
    Łukasz Kowalik, Arkadiusz Socała
    Czasopismo:
    Algorithmica (rok: 2016, tom: 74, strony: 1435–1452), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-015-0004-z - link do publikacji
  3. Certifying coloring algorithms for graphs without long induced paths
    Autorzy:
    Marcin Kamiński, Anna Pstrucha
    Czasopismo:
    Discrete Applied Mathematics (rok: 2019, tom: 261, strony: 258-267), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.dam.2018.09.031 - link do publikacji
  4. Hardness of approximation for strip packing
    Autorzy:
    Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk
    Czasopismo:
    ACM Transactions on Computation Theory (TOCT) (rok: 2017, tom: 9, strony: 14:1-14:7), Wydawca: ACM (Association for Computing Machinery)
    Status:
    Opublikowana
    Doi:
    10.1145/3092026 - link do publikacji
  5. Fixed-Parameter Tractability of Token Jumping on Planar Graphs
    Autorzy:
    Takehiro Ito, Marcin Kamiński, Hirotaka Ono
    Czasopismo:
    Discrete Applied Mathematics , Wydawca: Elsevier
    Status:
    Złożona
    Doi:
    brak - link do publikacji
  6. Constrained Multilinear Detection and Generalized Graph Motifs
    Autorzy:
    Andreas Björklund, Petteri Kaski, Lukasz Kowalik
    Czasopismo:
    Algorithmica (rok: 2016, tom: 74, strony: 947-967), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-015-9981-1 - link do publikacji
  7. Spotting Trees with Few Leaves
    Autorzy:
    Andreas Björklund, Vikram Kamat, Łukasz Kowalik, Meirav Zehavi
    Czasopismo:
    SIAM Journal on Discrete Mathematics (rok: 2017, tom: 31, strony: 687–713), Wydawca: SIAM
    Status:
    Opublikowana
    Doi:
    10.1137/15M1048975 - link do publikacji
  8. Linear Kernels for Outbranching Problems in Sparse Digraphs
    Autorzy:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała
    Czasopismo:
    Algorithmica (rok: 2017, tom: 79, strony: 159-188), Wydawca: Springer
    Status:
    Opublikowana
    Doi:
    10.1007/s00453-016-0244-6 - link do publikacji
  9. On finding rainbow and colorful paths
    Autorzy:
    Lukasz Kowalik, Juho Lauri
    Czasopismo:
    Theoretical Computer Science (rok: 2016, tom: 628, strony: 110-114), Wydawca: Elsevier
    Status:
    Opublikowana
    Doi:
    10.1016/j.tcs.2016.03.017 - link do publikacji
  10. Tight Lower Bound for the Channel Assignment Problem
    Autorzy:
    Arkadiusz Socała
    Czasopismo:
    ACM Transactions on Algorithms (rok: 2016, tom: 12, strony: 48:1-48:19), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/2876505 - link do publikacji
  11. Tight Lower Bounds on Graph Embedding Problems
    Autorzy:
    Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socała
    Czasopismo:
    Journal of the ACM (rok: 2017, tom: 64, strony: 18:1-18:22), Wydawca: ACM
    Status:
    Opublikowana
    Doi:
    10.1145/3051094 - link do publikacji
  1. Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering
    Autorzy:
    Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
    Konferencja:
    57th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2016) (rok: 2016, ), Wydawca: IEEE
    Data:
    konferencja 9-11 październik 2016
    Status:
    Opublikowana
  2. A 14k-kernel for Planar Feedback Vertex Set via Region Decomposition
    Autorzy:
    Marthe Bonamy, Łukasz Kowalik
    Konferencja:
    9th International Symposium on Parameterized and Exact Computation, IPEC'14 (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja wrzesien
    Status:
    Opublikowana
  3. On the Fine-Grained Complexity of Rainbow Coloring
    Autorzy:
    Lukasz Kowalik, Juho Lauri, Arkadiusz Socala
    Konferencja:
    European Symposium on Algorithms, ESA 2016 (rok: 2016, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja August 22-24, 2016
    Status:
    Opublikowana
    Doi:
    link do publikacji
  4. Approximation and Parameterized Complexity of Minimax Approval Voting
    Autorzy:
    Marek Cygan, Łukasz Kowalik, Arkadiusz Socała, Krzysztof Sornat
    Konferencja:
    Thirty-First AAAI Conference on Artificial Intelligence (rok: 2017, ), Wydawca: AAAI Press
    Data:
    konferencja February 4-9, 2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  5. Improving TSP tours using dynamic programming over tree decomposition
    Autorzy:
    Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
    Konferencja:
    European Symposium on Algorithms (ESA 2017) (rok: 2017, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Data:
    konferencja 4-6.09.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  6. Linear Kernels for Outbranching Problems in Sparse Digraphs
    Autorzy:
    Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala
    Konferencja:
    International Workshop on Parameterized and Exact Computation (IPEC) (rok: 2015, ), Wydawca: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Data:
    konferencja September 16-18, 2015
    Status:
    Opublikowana
    Doi:
    link do publikacji
  7. Minimum bisection is fixed parameter tractable
    Autorzy:
    Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh
    Konferencja:
    Symposium on Theory of Computing, (STOC 2014) (rok: 2014, ), Wydawca: ACM
    Data:
    konferencja May 31 - June 03, 2014
    Status:
    Opublikowana
  8. Assigning Channels via the Meet-in-the-Middle Approach
    Autorzy:
    Arkadiusz Socała, Łukasz Kowalik
    Konferencja:
    14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja czerwiec
    Status:
    Opublikowana
  9. Subexponential parameterized algorithms for graphs of polynomial growth
    Autorzy:
    Dániel Marx, Marcin Pilipczuk
    Konferencja:
    European Symposium on Algorithms (rok: 2017, ), Wydawca: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Data:
    konferencja 4-6.09.2017
    Status:
    Opublikowana
    Doi:
    link do publikacji
  10. Tight lower bound for the channel assignment problem
    Autorzy:
    Arkadiusz Socała
    Konferencja:
    Symposium on Discrete Algorithms (SODA) (rok: 2015, ), Wydawca: ACM
    Data:
    konferencja January 4-6, 2015
    Status:
    Opublikowana
    Doi:
    link do publikacji
  11. Engineering Motif Search for Large Graphs
    Autorzy:
    Andreas Björklund, Petteri Kaski, Lukasz Kowalik, Juho Lauri
    Konferencja:
    Algorithm Engineering and Experimentation (ALENEX) (rok: 2016, ), Wydawca: ACM
    Data:
    konferencja January 10, 2016.
    Status:
    Opublikowana
    Doi:
    link do publikacji
  12. Fast Witness Extraction Using a Decision Oracle
    Autorzy:
    Andreas Björklund, Petteri Kaski, Łukasz Kowalik
    Konferencja:
    22th Annual European Symposium on Algorithms (ESA 2014) (rok: 2014, ), Wydawca: Springer
    Data:
    konferencja wrzesien
    Status:
    Opublikowana
  13. Spotting Trees with Few Leaves
    Autorzy:
    Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
    Konferencja:
    International Colloquium on Automata, Languages and Programming (ICALP) (rok: 2015, ), Wydawca: Springer
    Data:
    konferencja lipiec 2015
    Status:
    Opublikowana
  14. Tight Bounds for Graph Homomorphism and Subgraph Isomorphism
    Autorzy:
    Marek Cygan, Fedor V. Fomin, Alexander Golovnev, Alexander S. Kulikov, Ivan Mihajlin, Jakub Pachocki, Arkadiusz Socala
    Konferencja:
    Symposium on Discrete Algorithms (SODA) (rok: 2016, ), Wydawca: ACM
    Data:
    konferencja January 10-12, 2016
    Status:
    Opublikowana
    Doi:
    link do publikacji

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy