Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Andreas Björklund. An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 15:1-15:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bjorklund:LIPIcs.STACS.2021.15, author = {Bj\"{o}rklund, Andreas}, title = {{An Asymptotically Fast Polynomial Space Algorithm for Hamiltonicity Detection in Sparse Directed Graphs}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {15:1--15:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.15}, URN = {urn:nbn:de:0030-drops-136601}, doi = {10.4230/LIPIcs.STACS.2021.15}, annote = {Keywords: Hamiltonian cycle, directed graph, worst case analysis algorithm} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Łukasz Kowalik and Konrad Majewski. The Asymmetric Travelling Salesman Problem In Sparse Digraphs. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kowalik_et_al:LIPIcs.IPEC.2020.23, author = {Kowalik, {\L}ukasz and Majewski, Konrad}, title = {{The Asymmetric Travelling Salesman Problem In Sparse Digraphs}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {23:1--23:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.23}, URN = {urn:nbn:de:0030-drops-133269}, doi = {10.4230/LIPIcs.IPEC.2020.23}, annote = {Keywords: asymmetric traveling salesman problem, Hamiltonian cycle, sparse graphs, exponential algorithm} }
Published in: LIPIcs, Volume 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Łukasz Kowalik, Marcin Mucha, Wojciech Nadara, Marcin Pilipczuk, Manuel Sorge, and Piotr Wygocki. The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 37:1-37:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kowalik_et_al:LIPIcs.IPEC.2020.37, author = {Kowalik, {\L}ukasz and Mucha, Marcin and Nadara, Wojciech and Pilipczuk, Marcin and Sorge, Manuel and Wygocki, Piotr}, title = {{The PACE 2020 Parameterized Algorithms and Computational Experiments Challenge: Treedepth}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {37:1--37:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-172-6}, ISSN = {1868-8969}, year = {2020}, volume = {180}, editor = {Cao, Yixin and Pilipczuk, Marcin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.37}, URN = {urn:nbn:de:0030-drops-133404}, doi = {10.4230/LIPIcs.IPEC.2020.37}, annote = {Keywords: computing treedepth, contest, implementation challenge, FPT} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Łukasz Kowalik, Shaohua Li, Wojciech Nadara, Marcin Smulewicz, and Magnus Wahlström. Many Visits TSP Revisited. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 66:1-66:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kowalik_et_al:LIPIcs.ESA.2020.66, author = {Kowalik, {\L}ukasz and Li, Shaohua and Nadara, Wojciech and Smulewicz, Marcin and Wahlstr\"{o}m, Magnus}, title = {{Many Visits TSP Revisited}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {66:1--66:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-162-7}, ISSN = {1868-8969}, year = {2020}, volume = {173}, editor = {Grandoni, Fabrizio and Herman, Grzegorz and Sanders, Peter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.66}, URN = {urn:nbn:de:0030-drops-129329}, doi = {10.4230/LIPIcs.ESA.2020.66}, annote = {Keywords: many visits traveling salesman problem, exponential algorithm} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Édouard Bonnet, Yoichi Iwata, Bart M. P. Jansen, and Łukasz Kowalik. Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bonnet_et_al:LIPIcs.ESA.2019.23, author = {Bonnet, \'{E}douard and Iwata, Yoichi and Jansen, Bart M. P. and Kowalik, {\L}ukasz}, title = {{Fine-Grained Complexity of k-OPT in Bounded-Degree Graphs for Solving TSP}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {23:1--23:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.23}, URN = {urn:nbn:de:0030-drops-111444}, doi = {10.4230/LIPIcs.ESA.2019.23}, annote = {Keywords: traveling salesman problem, k-OPT, bounded degree} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Lukasz Kowalik and Arkadiusz Socala. Tight Lower Bounds for List Edge Coloring. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kowalik_et_al:LIPIcs.SWAT.2018.28, author = {Kowalik, Lukasz and Socala, Arkadiusz}, title = {{Tight Lower Bounds for List Edge Coloring}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {28:1--28:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.28}, URN = {urn:nbn:de:0030-drops-88540}, doi = {10.4230/LIPIcs.SWAT.2018.28}, annote = {Keywords: list edge coloring, complexity, ETH lower bound} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, Arkadiusz Socala, and Marcin Wrochna. Tight Lower Bounds for the Complexity of Multicoloring. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bonamy_et_al:LIPIcs.ESA.2017.18, author = {Bonamy, Marthe and Kowalik, Lukasz and Pilipczuk, Michal and Socala, Arkadiusz and Wrochna, Marcin}, title = {{Tight Lower Bounds for the Complexity of Multicoloring}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {18:1--18:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.18}, URN = {urn:nbn:de:0030-drops-78527}, doi = {10.4230/LIPIcs.ESA.2017.18}, annote = {Keywords: multicoloring, Kneser graph homomorphism, ETH lower bound} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Marek Cygan, Lukasz Kowalik, and Arkadiusz Socala. Improving TSP Tours Using Dynamic Programming over Tree Decompositions. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{cygan_et_al:LIPIcs.ESA.2017.30, author = {Cygan, Marek and Kowalik, Lukasz and Socala, Arkadiusz}, title = {{Improving TSP Tours Using Dynamic Programming over Tree Decompositions}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.30}, URN = {urn:nbn:de:0030-drops-78539}, doi = {10.4230/LIPIcs.ESA.2017.30}, annote = {Keywords: TSP, treewidth, local search, XP algorithm, hardness in P} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Lukasz Kowalik, Juho Lauri, and Arkadiusz Socala. On the Fine-Grained Complexity of Rainbow Coloring. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{kowalik_et_al:LIPIcs.ESA.2016.58, author = {Kowalik, Lukasz and Lauri, Juho and Socala, Arkadiusz}, title = {{On the Fine-Grained Complexity of Rainbow Coloring}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {58:1--58:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.58}, URN = {urn:nbn:de:0030-drops-64001}, doi = {10.4230/LIPIcs.ESA.2016.58}, annote = {Keywords: graph coloring, computational complexity, lower bounds, exponential time hypothesis, FPT algorithms} }
Published in: LIPIcs, Volume 43, 10th International Symposium on Parameterized and Exact Computation (IPEC 2015)
Marthe Bonamy, Lukasz Kowalik, Michal Pilipczuk, and Arkadiusz Socala. Linear Kernels for Outbranching Problems in Sparse Digraphs. In 10th International Symposium on Parameterized and Exact Computation (IPEC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 43, pp. 199-211, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bonamy_et_al:LIPIcs.IPEC.2015.199, author = {Bonamy, Marthe and Kowalik, Lukasz and Pilipczuk, Michal and Socala, Arkadiusz}, title = {{Linear Kernels for Outbranching Problems in Sparse Digraphs}}, booktitle = {10th International Symposium on Parameterized and Exact Computation (IPEC 2015)}, pages = {199--211}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-92-7}, ISSN = {1868-8969}, year = {2015}, volume = {43}, editor = {Husfeldt, Thore and Kanj, Iyad}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2015.199}, URN = {urn:nbn:de:0030-drops-55839}, doi = {10.4230/LIPIcs.IPEC.2015.199}, annote = {Keywords: FPT algorithm, kernelization, outbranching, sparse graphs} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Andreas Björklund, Petteri Kaski, and Lukasz Kowalik. Probably Optimal Graph Motifs. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 20-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{bjorklund_et_al:LIPIcs.STACS.2013.20, author = {Bj\"{o}rklund, Andreas and Kaski, Petteri and Kowalik, Lukasz}, title = {{Probably Optimal Graph Motifs}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {20--31}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.20}, URN = {urn:nbn:de:0030-drops-39196}, doi = {10.4230/LIPIcs.STACS.2013.20}, annote = {Keywords: graph motif, FPT algorithm} }
Published in: Dagstuhl Seminar Proceedings, Volume 8431, Moderately Exponential Time Algorithms (2008)
Fedor V. Fomin, Kazuo Iwama, Dieter Kratsch, Petteri Kaski, Mikko Koivisto, Lukasz Kowalik, Yoshio Okamoto, Johan van Rooij, and Ryan Williams. 08431 Open Problems – Moderately Exponential Time Algorithms. In Moderately Exponential Time Algorithms. Dagstuhl Seminar Proceedings, Volume 8431, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{fomin_et_al:DagSemProc.08431.3, author = {Fomin, Fedor V. and Iwama, Kazuo and Kratsch, Dieter and Kaski, Petteri and Koivisto, Mikko and Kowalik, Lukasz and Okamoto, Yoshio and van Rooij, Johan and Williams, Ryan}, title = {{08431 Open Problems – Moderately Exponential Time Algorithms}}, booktitle = {Moderately Exponential Time Algorithms}, pages = {1--8}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8431}, editor = {Fedor V. Fomin and Kazuo Iwama and Dieter Kratsch}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08431.3}, URN = {urn:nbn:de:0030-drops-17986}, doi = {10.4230/DagSemProc.08431.3}, annote = {Keywords: Algorithms, NP-hard problems, Moderately Exponential Time Algorithms} }
Feedback for Dagstuhl Publishing