LIPIcs, Volume 126
STACS 2019, March 13-16, 2019, Berlin, Germany
Editors: Rolf Niedermeier and Christophe Paul
LIPIcs, Volume 96
STACS 2018, February 28 to March 3, 2018, Caen, France
Editors: Rolf Niedermeier and Brigitte Vallée
LIPIcs, Volume 58
MFCS 2016, August 22-26, 2016, Kraków, Poland
Editors: Piotr Faliszewski, Anca Muscholl, and Rolf Niedermeier
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-dev.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 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Philipp Zschoche. Restless Temporal Path Parameterized Above Lower Bounds. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{zschoche:LIPIcs.STACS.2023.55, author = {Zschoche, Philipp}, title = {{Restless Temporal Path Parameterized Above Lower Bounds}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {55:1--55: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.55}, URN = {urn:nbn:de:0030-drops-177077}, doi = {10.4230/LIPIcs.STACS.2023.55}, annote = {Keywords: temporal graphs, FPT, above-lower-bound parameterization} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Hjalmar Schulz, André Nichterlein, Rolf Niedermeier, and Christopher Weyand. Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{schulz_et_al:LIPIcs.IPEC.2022.25, author = {Schulz, Hjalmar and Nichterlein, Andr\'{e} and Niedermeier, Rolf and Weyand, Christopher}, title = {{Applying a Cut-Based Data Reduction Rule for Weighted Cluster Editing in Polynomial Time}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {25:1--25:14}, 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.25}, URN = {urn:nbn:de:0030-drops-173816}, doi = {10.4230/LIPIcs.IPEC.2022.25}, annote = {Keywords: Correlation Clustering, Minimum Cut, Maximum s-t-Flow} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Aleksander Figiel, Vincent Froese, André Nichterlein, and Rolf Niedermeier. There and Back Again: On Applying Data Reduction Rules by Undoing Others. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 53:1-53:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{figiel_et_al:LIPIcs.ESA.2022.53, author = {Figiel, Aleksander and Froese, Vincent and Nichterlein, Andr\'{e} and Niedermeier, Rolf}, title = {{There and Back Again: On Applying Data Reduction Rules by Undoing Others}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-169914}, doi = {10.4230/LIPIcs.ESA.2022.53}, annote = {Keywords: Kernelization, Preprocessing, Vertex Cover} }
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-dev.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 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)
Laurent Bulteau, Mark Jones, Rolf Niedermeier, and Till Tantau. An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 6:1-6:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bulteau_et_al:LIPIcs.CPM.2022.6, author = {Bulteau, Laurent and Jones, Mark and Niedermeier, Rolf and Tantau, Till}, title = {{An FPT-Algorithm for Longest Common Subsequence Parameterized by the Maximum Number of Deletions}}, booktitle = {33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022)}, pages = {6:1--6:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-234-1}, ISSN = {1868-8969}, year = {2022}, volume = {223}, editor = {Bannai, Hideo and Holub, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.6}, URN = {urn:nbn:de:0030-drops-161338}, doi = {10.4230/LIPIcs.CPM.2022.6}, annote = {Keywords: NP-hard string problems, multiple sequence alignment, center string, parameterized complexity, search tree algorithms, enumerative algorithms} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Pascal Kunz, Till Fluschnik, Rolf Niedermeier, and Malte Renken. Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 29:1-29:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{kunz_et_al:LIPIcs.SWAT.2022.29, author = {Kunz, Pascal and Fluschnik, Till and Niedermeier, Rolf and Renken, Malte}, title = {{Most Classic Problems Remain NP-Hard on Relative Neighborhood Graphs and Their Relatives}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {29:1--29:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.29}, URN = {urn:nbn:de:0030-drops-161891}, doi = {10.4230/LIPIcs.SWAT.2022.29}, annote = {Keywords: Proximity Graphs, Relatively Closest Graphs, Gabriel Graphs, 3-Colorability, Dominating Set, Feedback Vertex Set, Hamiltonian Cycle, Independent Set, Exponential-Time Hypothesis} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Temporal Connectivity: Coping with Foreseen and Unforeseen Delays. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fuchsle_et_al:LIPIcs.SAND.2022.17, author = {F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte}, title = {{Temporal Connectivity: Coping with Foreseen and Unforeseen Delays}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {17:1--17:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.17}, URN = {urn:nbn:de:0030-drops-159598}, doi = {10.4230/LIPIcs.SAND.2022.17}, annote = {Keywords: Paths and walks in temporal graphs, static expansions of temporal graphs, two-player games, flow computations, dynamic programming, PSPACE-completeness} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Danny Hermelin, Yuval Itzhaki, Hendrik Molter, and Rolf Niedermeier. Temporal Unit Interval Independent Sets. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 19:1-19:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hermelin_et_al:LIPIcs.SAND.2022.19, author = {Hermelin, Danny and Itzhaki, Yuval and Molter, Hendrik and Niedermeier, Rolf}, title = {{Temporal Unit Interval Independent Sets}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {19:1--19:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.19}, URN = {urn:nbn:de:0030-drops-159617}, doi = {10.4230/LIPIcs.SAND.2022.19}, annote = {Keywords: Temporal Graphs, Vertex Orderings, Order Preservation, Interval Graphs, Algorithms and Complexity} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Delay-Robust Routes in Temporal Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{fuchsle_et_al:LIPIcs.STACS.2022.30, author = {F\"{u}chsle, Eugen and Molter, Hendrik and Niedermeier, Rolf and Renken, Malte}, title = {{Delay-Robust Routes in Temporal Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {30:1--30:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra 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.2022.30}, URN = {urn:nbn:de:0030-drops-158403}, doi = {10.4230/LIPIcs.STACS.2022.30}, annote = {Keywords: algorithms and complexity, parameterized complexity, time-varying networks, temporal paths, journeys} }
Published in: Dagstuhl Reports, Volume 11, Issue 3 (2021)
Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier. Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171). In Dagstuhl Reports, Volume 11, Issue 3, pp. 16-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Article{casteigts_et_al:DagRep.11.3.16, author = {Casteigts, Arnaud and Meeks, Kitty and Mertzios, George B. and Niedermeier, Rolf}, title = {{Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171)}}, pages = {16--46}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {3}, editor = {Casteigts, Arnaud and Meeks, Kitty and Mertzios, George B. and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.11.3.16}, URN = {urn:nbn:de:0030-drops-146892}, doi = {10.4230/DagRep.11.3.16}, annote = {Keywords: algorithm engineering, complex network analysis, distributed computing, models and classes, parameterized complexity analysis} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Leon Kellerhals, Malte Renken, and Philipp Zschoche. Parameterized Algorithms for Diverse Multistage Problems. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 55:1-55:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{kellerhals_et_al:LIPIcs.ESA.2021.55, author = {Kellerhals, Leon and Renken, Malte and Zschoche, Philipp}, title = {{Parameterized Algorithms for Diverse Multistage Problems}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {55:1--55:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-204-4}, ISSN = {1868-8969}, year = {2021}, volume = {204}, editor = {Mutzel, Petra and Pagh, Rasmus 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.2021.55}, URN = {urn:nbn:de:0030-drops-146360}, doi = {10.4230/LIPIcs.ESA.2021.55}, annote = {Keywords: Temporal graphs, dissimilar solutions, fixed-parameter tractability, perfect matchings, s-t paths, committee election, spanning forests, matroids} }
Feedback for Dagstuhl Publishing