Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Hans L. Bodlaender, Édouard Bonnet, Lars Jaffke, Dušan Knop, Paloma T. Lima, Martin Milanič, Sebastian Ordyniak, Sukanya Pandey, and Ondřej Suchý. Treewidth Is NP-Complete on Cubic Graphs. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bodlaender_et_al:LIPIcs.IPEC.2023.7, author = {Bodlaender, Hans L. and Bonnet, \'{E}douard and Jaffke, Lars and Knop, Du\v{s}an and Lima, Paloma T. and Milani\v{c}, Martin and Ordyniak, Sebastian and Pandey, Sukanya and Such\'{y}, Ond\v{r}ej}, title = {{Treewidth Is NP-Complete on Cubic Graphs}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {7:1--7:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-305-8}, ISSN = {1868-8969}, year = {2023}, volume = {285}, editor = {Misra, Neeldhara and Wahlstr\"{o}m, Magnus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.7}, URN = {urn:nbn:de:0030-drops-194263}, doi = {10.4230/LIPIcs.IPEC.2023.7}, annote = {Keywords: Treewidth, cubic graphs, degree, NP-completeness} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Václav Blažej, Pratibha Choudhary, Dušan Knop, Šimon Schierreich, Ondřej Suchý, and Tomáš Valla. On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{blazej_et_al:LIPIcs.ESA.2022.22, author = {Bla\v{z}ej, V\'{a}clav and Choudhary, Pratibha and Knop, Du\v{s}an and Schierreich, \v{S}imon and Such\'{y}, Ond\v{r}ej and Valla, Tom\'{a}\v{s}}, title = {{On Polynomial Kernels for Traveling Salesperson Problem and Its Generalizations}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {22:1--22:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.22}, URN = {urn:nbn:de:0030-drops-169600}, doi = {10.4230/LIPIcs.ESA.2022.22}, annote = {Keywords: Traveling Salesperson, Subset TSP, Waypoint Routing, Kernelization} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Radovan Červený, Pratibha Choudhary, and Ondřej Suchý. On Kernels for d-Path Vertex Cover. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{cerveny_et_al:LIPIcs.MFCS.2022.29, author = {\v{C}erven\'{y}, Radovan and Choudhary, Pratibha and Such\'{y}, Ond\v{r}ej}, title = {{On Kernels for d-Path Vertex Cover}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {29:1--29:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.29}, URN = {urn:nbn:de:0030-drops-168279}, doi = {10.4230/LIPIcs.MFCS.2022.29}, annote = {Keywords: Parameterized complexity, Kernelization, d-Hitting Set, d-Path Vertex Cover, Expansion Lemma} }
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-dev.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 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Eduard Eiben, Dušan Knop, Fahad Panolan, and Ondřej Suchý. Complexity of the Steiner Network Problem with Respect to the Number of Terminals. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{eiben_et_al:LIPIcs.STACS.2019.25, author = {Eiben, Eduard and Knop, Du\v{s}an and Panolan, Fahad and Such\'{y}, Ond\v{r}ej}, title = {{Complexity of the Steiner Network Problem with Respect to the Number of Terminals}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {25:1--25:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.25}, URN = {urn:nbn:de:0030-drops-102642}, doi = {10.4230/LIPIcs.STACS.2019.25}, annote = {Keywords: Directed Steiner Network, Planar Graphs, Parameterized Algorithms, Bounded Genus, Exponential Time Hypothesis} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Junjie Luo, Hendrik Molter, and Ondrej Suchý. A Parameterized Complexity View on Collapsing k-Cores. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{luo_et_al:LIPIcs.IPEC.2018.7, author = {Luo, Junjie and Molter, Hendrik and Such\'{y}, Ondrej}, title = {{A Parameterized Complexity View on Collapsing k-Cores}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.7}, URN = {urn:nbn:de:0030-drops-102088}, doi = {10.4230/LIPIcs.IPEC.2018.7}, annote = {Keywords: r-Degenerate Vertex Deletion, Feedback Vertex Set, Fixed-Parameter Tractability, Kernelization Lower Bounds, Graph Algorithms, Social Network Analysis} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Jiehua Chen, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Cluster Editing in Multi-Layer and Temporal Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2018.24, author = {Chen, Jiehua and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej}, title = {{Cluster Editing in Multi-Layer and Temporal Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {24:1--24:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.24}, URN = {urn:nbn:de:0030-drops-99729}, doi = {10.4230/LIPIcs.ISAAC.2018.24}, annote = {Keywords: Cluster Editing, Temporal Graphs, Multi-Layer Graphs, Fixed-Parameter Algorithms, Polynomial Kernels, Parameterized Complexity} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
René van Bevern, Till Fluschnik, George B. Mertzios, Hendrik Molter, Manuel Sorge, and Ondrej Suchý. Finding Secluded Places of Special Interest in Graphs. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{vanbevern_et_al:LIPIcs.IPEC.2016.5, author = {van Bevern, Ren\'{e} and Fluschnik, Till and Mertzios, George B. and Molter, Hendrik and Sorge, Manuel and Such\'{y}, Ondrej}, title = {{Finding Secluded Places of Special Interest in Graphs}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {5:1--5:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.5}, URN = {urn:nbn:de:0030-drops-69380}, doi = {10.4230/LIPIcs.IPEC.2016.5}, annote = {Keywords: Neighborhood, Feedback Vertex Set, Vertex Deletion, Separator, Dominating Set} }
Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Archontia C. Giannopoulou, Daniel Lokshtanov, Saket Saurabh, and Ondrej Suchy. Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation). In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 85-96, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{giannopoulou_et_al:LIPIcs.FSTTCS.2014.85, author = {Giannopoulou, Archontia C. and Lokshtanov, Daniel and Saurabh, Saket and Suchy, Ondrej}, title = {{Tree Deletion Set Has a Polynomial Kernel (but no OPT^O(1) Approximation)}}, booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)}, pages = {85--96}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-77-4}, ISSN = {1868-8969}, year = {2014}, volume = {29}, editor = {Raman, Venkatesh and Suresh, S. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.85}, URN = {urn:nbn:de:0030-drops-48261}, doi = {10.4230/LIPIcs.FSTTCS.2014.85}, annote = {Keywords: Tree Deletion Set, Feedback Vertex Set, Kernelization, Linear Equations} }
Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Matthias Mnich, Geevarghese Philip, Saket Saurabh, and Ondrej Suchy. Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 412-423, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)
@InProceedings{mnich_et_al:LIPIcs.FSTTCS.2012.412, author = {Mnich, Matthias and Philip, Geevarghese and Saurabh, Saket and Suchy, Ondrej}, title = {{Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound}}, booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)}, pages = {412--423}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-47-7}, ISSN = {1868-8969}, year = {2012}, volume = {18}, editor = {D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.412}, URN = {urn:nbn:de:0030-drops-38776}, doi = {10.4230/LIPIcs.FSTTCS.2012.412}, annote = {Keywords: Algorithms and data structures; fixed-parameter algorithms; bipartite graphs; above-guarantee parameterization} }
Feedback for Dagstuhl Publishing