Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Klaus Heeger and Danny Hermelin. Minimizing the Weighted Number of Tardy Jobs Is W[1]-Hard. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heeger_et_al:LIPIcs.ESA.2024.68, author = {Heeger, Klaus and Hermelin, Danny}, title = {{Minimizing the Weighted Number of Tardy Jobs Is W\lbrack1\rbrack-Hard}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {68:1--68:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.68}, URN = {urn:nbn:de:0030-drops-211392}, doi = {10.4230/LIPIcs.ESA.2024.68}, annote = {Keywords: single-machine scheduling, number of different weights, number of different processing times} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Tesshu Hanaka, Michael Lampis, Manolis Vasilakis, and Kanae Yoshiwatari. Parameterized Vertex Integrity Revisited. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hanaka_et_al:LIPIcs.MFCS.2024.58, author = {Hanaka, Tesshu and Lampis, Michael and Vasilakis, Manolis and Yoshiwatari, Kanae}, title = {{Parameterized Vertex Integrity Revisited}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {58:1--58:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.58}, URN = {urn:nbn:de:0030-drops-206141}, doi = {10.4230/LIPIcs.MFCS.2024.58}, annote = {Keywords: Parameterized Complexity, Treedepth, Vertex Integrity} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Klaus Heeger, Danny Hermelin, Matthias Mnich, and Dvir Shabtay. No Polynomial Kernels for Knapsack. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 83:1-83:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{heeger_et_al:LIPIcs.ICALP.2024.83, author = {Heeger, Klaus and Hermelin, Danny and Mnich, Matthias and Shabtay, Dvir}, title = {{No Polynomial Kernels for Knapsack}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {83:1--83:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.83}, URN = {urn:nbn:de:0030-drops-202261}, doi = {10.4230/LIPIcs.ICALP.2024.83}, annote = {Keywords: Knapsack, polynomial kernels, compositions, number of different weights, number of different profits} }
Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Klaus Heeger, Danny Hermelin, and Dvir Shabtay. Single Machine Scheduling with Few Deadlines. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{heeger_et_al:LIPIcs.IPEC.2023.24, author = {Heeger, Klaus and Hermelin, Danny and Shabtay, Dvir}, title = {{Single Machine Scheduling with Few Deadlines}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {24:1--24:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.24}, URN = {urn:nbn:de:0030-drops-194434}, doi = {10.4230/LIPIcs.IPEC.2023.24}, annote = {Keywords: Single-machine scheduling, weighted completion time, tardy jobs, pseudopolynomial algorithms, parameterized complexity} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Matthias Bentert, Klaus Heeger, and Tomohiro Koana. Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bentert_et_al:LIPIcs.ESA.2023.16, author = {Bentert, Matthias and Heeger, Klaus and Koana, Tomohiro}, title = {{Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {16:1--16:16}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.16}, URN = {urn:nbn:de:0030-drops-186692}, doi = {10.4230/LIPIcs.ESA.2023.16}, annote = {Keywords: FPT in P, Algebraic Algorithms, Adaptive Algorithms, Subgraph Detection, Matching, APSP} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Klaus Heeger, André Nichterlein, and Rolf Niedermeier. Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{heeger_et_al:LIPIcs.STACS.2023.35, author = {Heeger, Klaus and Nichterlein, Andr\'{e} and Niedermeier, Rolf}, title = {{Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {35:1--35:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.35}, URN = {urn:nbn:de:0030-drops-176876}, doi = {10.4230/LIPIcs.STACS.2023.35}, annote = {Keywords: FPT in P, Kernelization, Decomposition} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Niclas Boehmer, Klaus Heeger, and Rolf Niedermeier. Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{boehmer_et_al:LIPIcs.MFCS.2022.21, author = {Boehmer, Niclas and Heeger, Klaus and Niedermeier, Rolf}, title = {{Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {21:1--21:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.21}, URN = {urn:nbn:de:0030-drops-168194}, doi = {10.4230/LIPIcs.MFCS.2022.21}, annote = {Keywords: Stable Marriage, Stable Roommates, adapting to changing preferences, NP-hardness, W\lbrack1\rbrack-hardness, XP, FPT, master lists, incremental algorithms} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Matthias Bentert, Klaus Heeger, and Dušan Knop. Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 36:1-36:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bentert_et_al:LIPIcs.ISAAC.2020.36, author = {Bentert, Matthias and Heeger, Klaus and Knop, Du\v{s}an}, title = {{Length-Bounded Cuts: Proper Interval Graphs and Structural Parameters}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {36:1--36:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.36}, URN = {urn:nbn:de:0030-drops-133800}, doi = {10.4230/LIPIcs.ISAAC.2020.36}, annote = {Keywords: Edge-disjoint paths, pathwidth, feedback vertex number} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Robert Bredereck, Klaus Heeger, Dušan Knop, and Rolf Niedermeier. Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bredereck_et_al:LIPIcs.ISAAC.2019.44, author = {Bredereck, Robert and Heeger, Klaus and Knop, Du\v{s}an and Niedermeier, Rolf}, title = {{Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.44}, URN = {urn:nbn:de:0030-drops-115406}, doi = {10.4230/LIPIcs.ISAAC.2019.44}, annote = {Keywords: Stable matching, acceptability graph, fixed-parameter tractability, W\lbrack1\rbrack-hardness, treewidth, treedepth, tree-cut width, feedback set numbers} }
Feedback for Dagstuhl Publishing