Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Stefan Kratsch and Pascal Kunz. Approximate Turing Kernelization and Lower Bounds for Domination Problems. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kratsch_et_al:LIPIcs.IPEC.2023.32, author = {Kratsch, Stefan and Kunz, Pascal}, title = {{Approximate Turing Kernelization and Lower Bounds for Domination Problems}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {32:1--32:17}, 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.32}, URN = {urn:nbn:de:0030-drops-194516}, doi = {10.4230/LIPIcs.IPEC.2023.32}, annote = {Keywords: Approximate Turing kernelization, approximation lower bounds, exponential-time hypothesis, dominating set, capacitated dominating, connected dominating set, independent dominating set, treewidth, vertex cover number} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Falko Hegerfeld and Stefan Kratsch. Tight Algorithms for Connectivity Problems Parameterized by Clique-Width. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 59:1-59:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{hegerfeld_et_al:LIPIcs.ESA.2023.59, author = {Hegerfeld, Falko and Kratsch, Stefan}, title = {{Tight Algorithms for Connectivity Problems Parameterized by Clique-Width}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {59:1--59:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.59}, URN = {urn:nbn:de:0030-drops-187124}, doi = {10.4230/LIPIcs.ESA.2023.59}, annote = {Keywords: Parameterized Complexity, Connectivity, Clique-width, Cut\&Count, Lower Bound} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Vera Chekan and Stefan Kratsch. Tight Algorithmic Applications of Clique-Width Generalizations. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chekan_et_al:LIPIcs.MFCS.2023.35, author = {Chekan, Vera and Kratsch, Stefan}, title = {{Tight Algorithmic Applications of Clique-Width Generalizations}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.35}, URN = {urn:nbn:de:0030-drops-185699}, doi = {10.4230/LIPIcs.MFCS.2023.35}, annote = {Keywords: Parameterized complexity, connectivity problems, clique-width} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Narek Bojikian, Vera Chekan, Falko Hegerfeld, and Stefan Kratsch. Tight Bounds for Connectivity Problems Parameterized by Cutwidth. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 14:1-14:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bojikian_et_al:LIPIcs.STACS.2023.14, author = {Bojikian, Narek and Chekan, Vera and Hegerfeld, Falko and Kratsch, Stefan}, title = {{Tight Bounds for Connectivity Problems Parameterized by Cutwidth}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {14:1--14:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.14}, URN = {urn:nbn:de:0030-drops-176667}, doi = {10.4230/LIPIcs.STACS.2023.14}, annote = {Keywords: Parameterized complexity, connectivity problems, cutwidth} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Falko Hegerfeld and Stefan Kratsch. Towards Exact Structural Thresholds for Parameterized Complexity. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hegerfeld_et_al:LIPIcs.IPEC.2022.17, author = {Hegerfeld, Falko and Kratsch, Stefan}, title = {{Towards Exact Structural Thresholds for Parameterized Complexity}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {17:1--17:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.17}, URN = {urn:nbn:de:0030-drops-173734}, doi = {10.4230/LIPIcs.IPEC.2022.17}, annote = {Keywords: Parameterized complexity, lower bound, vertex cover, odd cycle transversal, SETH, modulator, treedepth, cliquewidth} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Dušan Knop and Martin Koutecký. Scheduling Kernels via Configuration LP. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 73:1-73:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{knop_et_al:LIPIcs.ESA.2022.73, author = {Knop, Du\v{s}an and Kouteck\'{y}, Martin}, title = {{Scheduling Kernels via Configuration LP}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {73:1--73:15}, 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.73}, URN = {urn:nbn:de:0030-drops-170118}, doi = {10.4230/LIPIcs.ESA.2022.73}, annote = {Keywords: Scheduling, Kernelization} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Jianer Chen, Qin Huang, Iyad Kanj, Qian Li, and Ge Xia. Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 48:1-48:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2021.48, author = {Chen, Jianer and Huang, Qin and Kanj, Iyad and Li, Qian and Xia, Ge}, title = {{Streaming Algorithms for Graph k-Matching with Optimal or Near-Optimal Update Time}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {48:1--48:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.48}, URN = {urn:nbn:de:0030-drops-154816}, doi = {10.4230/LIPIcs.ISAAC.2021.48}, annote = {Keywords: streaming algorithms, matching, parameterized algorithms, lower bounds} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Júlio Araújo, Marin Bougeret, Victor Campos, and Ignasi Sau. A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{araujo_et_al:LIPIcs.IPEC.2021.4, author = {Ara\'{u}jo, J\'{u}lio and Bougeret, Marin and Campos, Victor and Sau, Ignasi}, title = {{A New Framework for Kernelization Lower Bounds: The Case of Maximum Minimal Vertex Cover}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.4}, URN = {urn:nbn:de:0030-drops-153879}, doi = {10.4230/LIPIcs.IPEC.2021.4}, annote = {Keywords: Maximum minimal vertex cover, parameterized complexity, polynomial kernel, kernelization lower bound, Erd\H{o}s-Hajnal property, induced subgraphs} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Approximate Turing Kernelization for Problems Parameterized by Treewidth. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 60:1-60:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hols_et_al:LIPIcs.ESA.2020.60, author = {Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid}, title = {{Approximate Turing Kernelization for Problems Parameterized by Treewidth}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {60:1--60:23}, 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.60}, URN = {urn:nbn:de:0030-drops-129261}, doi = {10.4230/LIPIcs.ESA.2020.60}, annote = {Keywords: Approximation, Turing kernelization, Graph problems, Treewidth} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Falko Hegerfeld and Stefan Kratsch. Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hegerfeld_et_al:LIPIcs.STACS.2020.29, author = {Hegerfeld, Falko and Kratsch, Stefan}, title = {{Solving Connectivity Problems Parameterized by Treedepth in Single-Exponential Time and Polynomial Space}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.29}, URN = {urn:nbn:de:0030-drops-118907}, doi = {10.4230/LIPIcs.STACS.2020.29}, annote = {Keywords: Parameterized Complexity, Connectivity, Treedepth, Cut\&Count, Polynomial Space} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Eva-Maria C. Hols, Stefan Kratsch, and Astrid Pieterse. Elimination Distances, Blocking Sets, and Kernels for Vertex Cover. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{hols_et_al:LIPIcs.STACS.2020.36, author = {Hols, Eva-Maria C. and Kratsch, Stefan and Pieterse, Astrid}, title = {{Elimination Distances, Blocking Sets, and Kernels for Vertex Cover}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.36}, URN = {urn:nbn:de:0030-drops-118974}, doi = {10.4230/LIPIcs.STACS.2020.36}, annote = {Keywords: Vertex Cover, kernelization, blocking sets, elimination distance, structural parameters} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Stefan Kratsch and Florian Nelles. Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 38:1-38:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kratsch_et_al:LIPIcs.STACS.2020.38, author = {Kratsch, Stefan and Nelles, Florian}, title = {{Efficient Parameterized Algorithms for Computing All-Pairs Shortest Paths}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {38:1--38:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.38}, URN = {urn:nbn:de:0030-drops-118992}, doi = {10.4230/LIPIcs.STACS.2020.38}, annote = {Keywords: All-pairs shortest Paths, efficient parameterized Algorithms, parameterized Complexity, Clique-width, Modular-width} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Fabrizio Grandoni, Stefan Kratsch, and Andreas Wiese. Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{grandoni_et_al:LIPIcs.ESA.2019.53, author = {Grandoni, Fabrizio and Kratsch, Stefan and Wiese, Andreas}, title = {{Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {53:1--53:16}, 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.53}, URN = {urn:nbn:de:0030-drops-111741}, doi = {10.4230/LIPIcs.ESA.2019.53}, annote = {Keywords: parameterized approximation, parameterized intractability, independent set of rectangles, geometric knapsack} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Falko Hegerfeld and Stefan Kratsch. On Adaptive Algorithms for Maximum Matching. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 71:1-71:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hegerfeld_et_al:LIPIcs.ICALP.2019.71, author = {Hegerfeld, Falko and Kratsch, Stefan}, title = {{On Adaptive Algorithms for Maximum Matching}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {71:1--71:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.71}, URN = {urn:nbn:de:0030-drops-106477}, doi = {10.4230/LIPIcs.ICALP.2019.71}, annote = {Keywords: Matchings, Adaptive Analysis, Parameterized Complexity} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Eva-Maria C. Hols and Stefan Kratsch. On Kernelization for Edge Dominating Set under Structural Parameters. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hols_et_al:LIPIcs.STACS.2019.36, author = {Hols, Eva-Maria C. and Kratsch, Stefan}, title = {{On Kernelization for Edge Dominating Set under Structural Parameters}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {36:1--36:18}, 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.36}, URN = {urn:nbn:de:0030-drops-102752}, doi = {10.4230/LIPIcs.STACS.2019.36}, annote = {Keywords: Edge dominating set, kernelization, structural parameters} }
Feedback for Dagstuhl Publishing