Current trends in parameterized and exponential-time algorithms

2013/09/B/ST6/03136

Keywords

Descriptors

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

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)

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
2014-03-21
Project end date
2017-03-20
Project duration
36 months (the same as in the proposal)
Project status
Project settled

Equipment purchased [PL]

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

Information in the final report

Publication in academic press/journals (10)

  1. Certifying coloring algorithms for graphs without long induced paths

    Authors:
    Marcin Kamiński, Anna Pstrucha
    Academic press:
    Discrete Applied Mathematics (year: 2019, volume: 261, pages: 258-267), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.dam.2018.09.031 – link to the publication
  2. Linear Kernels for Outbranching Problems in Sparse Digraphs

    Authors:
    Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała
    Academic press:
    Algorithmica (year: 2017, volume: 79, pages: 159-188), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-016-0244-6 – link to the publication
  3. 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 (year: 2017, volume: 64, pages: 18:1-18:22), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/3051094 – link to the publication
  4. Spotting Trees with Few Leaves

    Authors:
    Andreas Björklund, Vikram Kamat, Łukasz Kowalik, Meirav Zehavi
    Academic press:
    SIAM Journal on Discrete Mathematics (year: 2017, volume: 31, pages: 687–713), Publisher: SIAM
    Status:
    Published
    DOI:
    10.1137/15M1048975 – link to the publication
  5. On finding rainbow and colorful paths

    Authors:
    Lukasz Kowalik, Juho Lauri
    Academic press:
    Theoretical Computer Science (year: 2016, volume: 628, pages: 110-114), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.03.017 – link to the publication
  6. A 13k-kernel for planar feedback vertex set via region decomposition

    Authors:
    Marthe Bonamy, Lukasz Kowalik
    Academic press:
    Theoretical Computer Science (year: 2016, volume: 645, pages: 25-40), Publisher: Elsevier
    Status:
    Published
    DOI:
    10.1016/j.tcs.2016.05.031 – link to the publication
  7. Hardness of approximation for strip packing

    Authors:
    Anna Adamaszek, Tomasz Kociumaka, Marcin Pilipczuk, Michal Pilipczuk
    Academic press:
    ACM Transactions on Computation Theory (TOCT) (year: 2017, volume: 9, pages: 14:1-14:7), Publisher: ACM (Association for Computing Machinery)
    Status:
    Published
    DOI:
    10.1145/3092026 – link to the publication
  8. Tight Lower Bound for the Channel Assignment Problem

    Authors:
    Arkadiusz Socała
    Academic press:
    ACM Transactions on Algorithms (year: 2016, volume: 12, pages: 48:1-48:19), Publisher: ACM
    Status:
    Published
    DOI:
    10.1145/2876505 – link to the publication
  9. Assigning Channels Via the Meet-in-the-Middle Approach

    Authors:
    Łukasz Kowalik, Arkadiusz Socała
    Academic press:
    Algorithmica (year: 2016, volume: 74, pages: 1435–1452), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-015-0004-z – link to the publication
  10. Constrained Multilinear Detection and Generalized Graph Motifs

    Authors:
    Andreas Björklund, Petteri Kaski, Lukasz Kowalik
    Academic press:
    Algorithmica (year: 2016, volume: 74, pages: 947-967), Publisher: Springer
    Status:
    Published
    DOI:
    10.1007/s00453-015-9981-1 – link to the publication

Articles in post-conference publications (14)

  1. Fast Witness Extraction Using a Decision Oracle

    Authors:
    Andreas Björklund, Petteri Kaski, Łukasz Kowalik
    Conference:
    22th Annual European Symposium on Algorithms (ESA 2014) (year: 2014, pages: 149-160), Publisher: Springer
    Date:
    conference wrzesien
    Status:
    Published
  2. 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) (year: 2014, pages: 282-293), Publisher: Springer
    Date:
    conference czerwiec
    Status:
    Published
  3. 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) (year: 2016, pages: 515-524), Publisher: IEEE
    Date:
    conference 9-11 październik 2016
    Status:
    Published
  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 (year: 2017, pages: 459-465), Publisher: AAAI Press
    Date:
    conference February 4-9, 2017
    Status:
    Published
    DOI:
    link to the publication
  5. On the Fine-Grained Complexity of Rainbow Coloring

    Authors:
    Lukasz Kowalik, Juho Lauri, Arkadiusz Socala
    Conference:
    European Symposium on Algorithms, ESA 2016 (year: 2016, pages: 58:1-58:16), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference August 22-24, 2016
    Status:
    Published
    DOI:
    link to the publication
  6. Subexponential parameterized algorithms for graphs of polynomial growth

    Authors:
    Dániel Marx, Marcin Pilipczuk
    Conference:
    European Symposium on Algorithms (year: 2017, pages: 59:1-59:15), Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Date:
    conference 4-6.09.2017
    Status:
    Published
    DOI:
    link to the publication
  7. Improving TSP tours using dynamic programming over tree decomposition

    Authors:
    Marek Cygan, Lukasz Kowalik, Arkadiusz Socala
    Conference:
    European Symposium on Algorithms (ESA 2017) (year: 2017, pages: 30:1-30:14), Publisher: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
    Date:
    conference 4-6.09.2017
    Status:
    Published
    DOI:
    link to the publication
  8. Tight lower bound for the channel assignment problem

    Authors:
    Arkadiusz Socała
    Conference:
    Symposium on Discrete Algorithms (SODA) (year: 2015, pages: 662-675), Publisher: ACM
    Date:
    conference January 4-6, 2015
    Status:
    Published
    DOI:
    link to the publication
  9. Spotting Trees with Few Leaves

    Authors:
    Andreas Björklund, Vikram Kamat, Lukasz Kowalik, Meirav Zehavi
    Conference:
    International Colloquium on Automata, Languages and Programming (ICALP) (year: 2015, pages: 243-255), Publisher: Springer
    Date:
    conference lipiec 2015
    Status:
    Published
  10. 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) (year: 2014, pages: 323--332), Publisher: ACM
    Date:
    conference May 31 - June 03, 2014
    Status:
    Published
  11. 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 (year: 2014, pages: 97-109), Publisher: Springer
    Date:
    conference wrzesien
    Status:
    Published
  12. 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) (year: 2016, pages: 1643-1649), Publisher: ACM
    Date:
    conference January 10-12, 2016
    Status:
    Published
    DOI:
    link to the publication
  13. 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) (year: 2015, pages: 199-211), Publisher: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik
    Date:
    conference September 16-18, 2015
    Status:
    Published
    DOI:
    link to the publication
  14. Engineering Motif Search for Large Graphs

    Authors:
    Andreas Björklund, Petteri Kaski, Lukasz Kowalik, Juho Lauri
    Conference:
    Algorithm Engineering and Experimentation (ALENEX) (year: 2016, pages: 104-118), Publisher: ACM
    Date:
    conference January 10, 2016.
    Status:
    Published
    DOI:
    link to the publication

« New search

Graphic design and implementation: Jakub Piotrowski