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
Principal investigator (from the host institution)
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]
- komputer z monitorem. Cost: 4 000 PLN
- laptop.
- laptop ze stacją dokującą, klawiaturą i monitorem. Cost: 6 000 PLN
Information in the final report
Publication in academic press/journals (10)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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)
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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
-
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