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.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.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.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.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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the Domination Number of Graphs via Edge Contractions. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{galby_et_al:LIPIcs.MFCS.2019.41, author = {Galby, Esther and Lima, Paloma T. and Ries, Bernard}, title = {{Reducing the Domination Number of Graphs via Edge Contractions}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {41:1--41:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.41}, URN = {urn:nbn:de:0030-drops-109856}, doi = {10.4230/LIPIcs.MFCS.2019.41}, annote = {Keywords: domination number, blocker problem, graph classes} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Lars Jaffke and Paloma T. Lima. A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 34:1-34:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jaffke_et_al:LIPIcs.MFCS.2019.34, author = {Jaffke, Lars and Lima, Paloma T.}, title = {{A Complexity Dichotomy for Critical Values of the b-Chromatic Number of Graphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {34:1--34:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.34}, URN = {urn:nbn:de:0030-drops-109784}, doi = {10.4230/LIPIcs.MFCS.2019.34}, annote = {Keywords: b-Coloring, b-Chromatic Number} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{knop_et_al:LIPIcs.MFCS.2019.33, author = {Knop, Du\v{s}an and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Toufar, Tom\'{a}\v{s}}, title = {{Parameterized Complexity of Fair Vertex Evaluation Problems}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {33:1--33:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.33}, URN = {urn:nbn:de:0030-drops-109775}, doi = {10.4230/LIPIcs.MFCS.2019.33}, annote = {Keywords: Fair objective, metatheorem, fair vertex cover, twin cover, modular width} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Radovan Červený and Ondřej Suchý. Faster FPT Algorithm for 5-Path Vertex Cover. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cerveny_et_al:LIPIcs.MFCS.2019.32, author = {\v{C}erven\'{y}, Radovan and Such\'{y}, Ond\v{r}ej}, title = {{Faster FPT Algorithm for 5-Path Vertex Cover}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {32:1--32:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.32}, URN = {urn:nbn:de:0030-drops-109761}, doi = {10.4230/LIPIcs.MFCS.2019.32}, annote = {Keywords: graph algorithms, Hitting Set, iterative compression, parameterized complexity, d-Path Vertex Cover} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Eduard Eiben, Robert Ganian, Thekla Hamm, and O-joung Kwon. Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 42:1-42:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{eiben_et_al:LIPIcs.MFCS.2019.42, author = {Eiben, Eduard and Ganian, Robert and Hamm, Thekla and Kwon, O-joung}, title = {{Measuring what Matters: A Hybrid Approach to Dynamic Programming with Treewidth}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {42:1--42:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.42}, URN = {urn:nbn:de:0030-drops-109867}, doi = {10.4230/LIPIcs.MFCS.2019.42}, annote = {Keywords: Parameterized complexity, treewidth, rank-width, fixed-parameter algorithms} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gaspers_et_al:LIPIcs.MFCS.2019.74, author = {Gaspers, Serge and Li, Ray}, title = {{Enumeration of Preferred Extensions in Almost Oriented Digraphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {74:1--74:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.74}, URN = {urn:nbn:de:0030-drops-110188}, doi = {10.4230/LIPIcs.MFCS.2019.74}, annote = {Keywords: abstract argumentation, exact algorithms, exponential time algorithms, parameterized algorithms, enumeration algorithms, semikernels in digraphs} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, and Saket Saurabh. Parameterized Complexity of Conflict-Free Matchings and Paths. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agrawal_et_al:LIPIcs.MFCS.2019.35, author = {Agrawal, Akanksha and Jain, Pallavi and Kanesh, Lawqueen and Saurabh, Saket}, title = {{Parameterized Complexity of Conflict-Free Matchings and Paths}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.35}, URN = {urn:nbn:de:0030-drops-109798}, doi = {10.4230/LIPIcs.MFCS.2019.35}, annote = {Keywords: Conflict-free, Matching, Shortest Path, FPT algorithm, W\lbrack1\rbrack-hard, Matroid} }
Published in: LIPIcs, Volume 135, 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)
Bryan O'Gorman. Parameterization of Tensor Network Contraction. In 14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 135, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ogorman:LIPIcs.TQC.2019.10, author = {O'Gorman, Bryan}, title = {{Parameterization of Tensor Network Contraction}}, booktitle = {14th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2019)}, pages = {10:1--10:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-112-2}, ISSN = {1868-8969}, year = {2019}, volume = {135}, editor = {van Dam, Wim and Man\v{c}inska, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2019.10}, URN = {urn:nbn:de:0030-drops-104025}, doi = {10.4230/LIPIcs.TQC.2019.10}, annote = {Keywords: tensor networks, parameterized complexity, tree embedding, congestion} }
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.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.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} }
Feedback for Dagstuhl Publishing