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 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 180, 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)
Leon Kellerhals and Tomohiro Koana. Parameterized Complexity of Geodetic Set. In 15th International Symposium on Parameterized and Exact Computation (IPEC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 180, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kellerhals_et_al:LIPIcs.IPEC.2020.20, author = {Kellerhals, Leon and Koana, Tomohiro}, title = {{Parameterized Complexity of Geodetic Set}}, booktitle = {15th International Symposium on Parameterized and Exact Computation (IPEC 2020)}, pages = {20:1--20:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2020.20}, URN = {urn:nbn:de:0030-drops-133237}, doi = {10.4230/LIPIcs.IPEC.2020.20}, annote = {Keywords: NP-hard graph problems, Shortest paths, Tree-likeness, Parameter hierarchy, Data reduction, Integer linear programming} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Till Fluschnik, Rolf Niedermeier, Carsten Schubert, and Philipp Zschoche. Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{fluschnik_et_al:LIPIcs.ISAAC.2020.43, author = {Fluschnik, Till and Niedermeier, Rolf and Schubert, Carsten and Zschoche, Philipp}, title = {{Multistage s-t Path: Confronting Similarity with Dissimilarity in Temporal Graphs}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {43:1--43:16}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.43}, URN = {urn:nbn:de:0030-drops-133879}, doi = {10.4230/LIPIcs.ISAAC.2020.43}, annote = {Keywords: Temporal graphs, shortest paths, consecutive similarity, consecutive dissimilarity, parameterized complexity, kernelization, representative sets in temporal graphs} }
Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Tomohiro Koana, Vincent Froese, and Rolf Niedermeier. Parameterized Algorithms for Matrix Completion with Radius Constraints. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{koana_et_al:LIPIcs.CPM.2020.20, author = {Koana, Tomohiro and Froese, Vincent and Niedermeier, Rolf}, title = {{Parameterized Algorithms for Matrix Completion with Radius Constraints}}, booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-149-8}, ISSN = {1868-8969}, year = {2020}, volume = {161}, editor = {G{\o}rtz, Inge Li and Weimann, Oren}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.20}, URN = {urn:nbn:de:0030-drops-121456}, doi = {10.4230/LIPIcs.CPM.2020.20}, annote = {Keywords: fixed-parameter tractability, consensus string problems, Closest String, Closest String with Wildcards} }
Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Nathan Schaar, Vincent Froese, and Rolf Niedermeier. Faster Binary Mean Computation Under Dynamic Time Warping. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{schaar_et_al:LIPIcs.CPM.2020.28, author = {Schaar, Nathan and Froese, Vincent and Niedermeier, Rolf}, title = {{Faster Binary Mean Computation Under Dynamic Time Warping}}, booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)}, pages = {28:1--28:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-149-8}, ISSN = {1868-8969}, year = {2020}, volume = {161}, editor = {G{\o}rtz, Inge Li and Weimann, Oren}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.28}, URN = {urn:nbn:de:0030-drops-121538}, doi = {10.4230/LIPIcs.CPM.2020.28}, annote = {Keywords: consensus string problems, time series averaging, minimum 1-separated sum, sparse strings} }
Published in: LIPIcs, Volume 148, 14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Till Fluschnik, Rolf Niedermeier, Valentin Rohm, and Philipp Zschoche. Multistage Vertex Cover. In 14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 148, pp. 14:1-14:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fluschnik_et_al:LIPIcs.IPEC.2019.14, author = {Fluschnik, Till and Niedermeier, Rolf and Rohm, Valentin and Zschoche, Philipp}, title = {{Multistage Vertex Cover}}, booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)}, pages = {14:1--14:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-129-0}, ISSN = {1868-8969}, year = {2019}, volume = {148}, editor = {Jansen, Bart M. P. and Telle, Jan Arne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2019.14}, URN = {urn:nbn:de:0030-drops-114753}, doi = {10.4230/LIPIcs.IPEC.2019.14}, annote = {Keywords: NP-hardness, dynamic graph problems, temporal graphs, time-evolving networks, W\lbrack1\rbrack-hardness, fixed-parameter tractability, kernelization} }
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-dev.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} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, and Florian Sikora. Token Sliding on Split Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{belmonte_et_al:LIPIcs.STACS.2019.13, author = {Belmonte, R\'{e}my and Kim, Eun Jung and Lampis, Michael and Mitsou, Valia and Otachi, Yota and Sikora, Florian}, title = {{Token Sliding on Split Graphs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {13:1--13: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.13}, URN = {urn:nbn:de:0030-drops-102529}, doi = {10.4230/LIPIcs.STACS.2019.13}, annote = {Keywords: reconfiguration, independent set, split graph} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
María Emilia Descotte, Diego Figueira, and Santiago Figueira. Closure Properties of Synchronized Relations. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{descotte_et_al:LIPIcs.STACS.2019.22, author = {Descotte, Mar{\'\i}a Emilia and Figueira, Diego and Figueira, Santiago}, title = {{Closure Properties of Synchronized Relations}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {22:1--22: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.22}, URN = {urn:nbn:de:0030-drops-102614}, doi = {10.4230/LIPIcs.STACS.2019.22}, annote = {Keywords: synchronized word relations, rational, closure, characterization, intersection, complement, Kleene star, concatenation} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Stasys Jukna and Andrzej Lingas. Lower Bounds for DeMorgan Circuits of Bounded Negation Width. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 41:1-41:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{jukna_et_al:LIPIcs.STACS.2019.41, author = {Jukna, Stasys and Lingas, Andrzej}, title = {{Lower Bounds for DeMorgan Circuits of Bounded Negation Width}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {41:1--41: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.41}, URN = {urn:nbn:de:0030-drops-102801}, doi = {10.4230/LIPIcs.STACS.2019.41}, annote = {Keywords: Boolean circuits, monotone circuits, lower bounds} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Stefan Kiefer and Corto Mascle. On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 43:1-43:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kiefer_et_al:LIPIcs.STACS.2019.43, author = {Kiefer, Stefan and Mascle, Corto}, title = {{On Finite Monoids over Nonnegative Integer Matrices and Short Killing Words}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {43:1--43:13}, 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.43}, URN = {urn:nbn:de:0030-drops-102823}, doi = {10.4230/LIPIcs.STACS.2019.43}, annote = {Keywords: matrix semigroups, unambiguous automata, codes, Restivo’s conjecture} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Sandeep Sen. A Unified Approach to Tail Estimates for Randomized Incremental Construction. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sen:LIPIcs.STACS.2019.58, author = {Sen, Sandeep}, title = {{A Unified Approach to Tail Estimates for Randomized Incremental Construction}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {58:1--58:16}, 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.58}, URN = {urn:nbn:de:0030-drops-102977}, doi = {10.4230/LIPIcs.STACS.2019.58}, annote = {Keywords: ric, tail estimates, martingale, lower bound} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Bas A. M. van Geffen, Bart M. P. Jansen, Arnoud A. W. M. de Kroon, and Rolf Morel. Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{vangeffen_et_al:LIPIcs.IPEC.2018.3, author = {van Geffen, Bas A. M. and Jansen, Bart M. P. and de Kroon, Arnoud A. W. M. and Morel, Rolf}, title = {{Lower Bounds for Dynamic Programming on Planar Graphs of Bounded Cutwidth}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {3:1--3: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.3}, URN = {urn:nbn:de:0030-drops-102049}, doi = {10.4230/LIPIcs.IPEC.2018.3}, annote = {Keywords: planarization, dominating set, cutwidth, lower bounds, strong exponential time hypothesis} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Rémy Belmonte, Michael Lampis, and Valia Mitsou. Parameterized (Approximate) Defective Coloring. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 10:1-10:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{belmonte_et_al:LIPIcs.STACS.2018.10, author = {Belmonte, R\'{e}my and Lampis, Michael and Mitsou, Valia}, title = {{Parameterized (Approximate) Defective Coloring}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {10:1--10:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.10}, URN = {urn:nbn:de:0030-drops-85304}, doi = {10.4230/LIPIcs.STACS.2018.10}, annote = {Keywords: Treewidth, Parameterized Complexity, Approximation, Coloring} }
Feedback for Dagstuhl Publishing