Projects funded by the NCN

Information on the principal investigator and host institution

Information of the project and the call

Keywords

Equipment

Delete all

Current trends in parameterized and exponential-time algorithms

2013/09/B/ST6/03136

Keywords:

algorithms parameterized complexity kernelization exponential-time algorithms

Descriptors:

  • ST6_6: Algorithms, parallel, distributed and network algorithms, algorithmic game theory

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

dr hab. Łukasz Kowalik 

Number of co-investigators in the project: 5

Call: OPUS 5 - announced on 2013-03-15

Amount awarded: 603 180 PLN

Project start date (Y-m-d): 2014-03-21

Project end date (Y-m-d): 2017-03-20

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

Project status: Project settled

Equipment purchased [PL]

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

Information in the final report

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

O Narodowym Centrum Nauki

Finansowanie nauki

Współpraca zagraniczna

Centrum prasowe

Deklaracja dostępności
Przetwarzanie danych osobowych
Polityka cookies

Partnerzy