Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
Jaroslav Garvardt, Malte Renken, Jannik Schestag, and Mathias Weller. Finding Degree-Constrained Acyclic Orientations. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{garvardt_et_al:LIPIcs.IPEC.2023.19, author = {Garvardt, Jaroslav and Renken, Malte and Schestag, Jannik and Weller, Mathias}, title = {{Finding Degree-Constrained Acyclic Orientations}}, booktitle = {18th International Symposium on Parameterized and Exact Computation (IPEC 2023)}, pages = {19:1--19:14}, 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.19}, URN = {urn:nbn:de:0030-drops-194383}, doi = {10.4230/LIPIcs.IPEC.2023.19}, annote = {Keywords: Graph Orientation, Phylogenetic Networks, General Factor, NP-hardness, Parameterized Algorithms, Treewidth} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Ruben Becker, Arnaud Casteigts, Pierluigi Crescenzi, Bojana Kodric, Malte Renken, Michael Raskin, and Viktor Zamaraev. Giant Components in Random Temporal Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{becker_et_al:LIPIcs.APPROX/RANDOM.2023.29, author = {Becker, Ruben and Casteigts, Arnaud and Crescenzi, Pierluigi and Kodric, Bojana and Renken, Malte and Raskin, Michael and Zamaraev, Viktor}, title = {{Giant Components in Random Temporal Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.29}, URN = {urn:nbn:de:0030-drops-188542}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.29}, annote = {Keywords: random temporal graph, Erd\H{o}s–R\'{e}nyi random graph, sharp threshold, temporal connectivity, temporal connected component, edge-ordered graph} }
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.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.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 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.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: 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.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} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 75:1-75:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{mertzios_et_al:LIPIcs.MFCS.2021.75, author = {Mertzios, George B. and Molter, Hendrik and Renken, Malte and Spirakis, Paul G. and Zschoche, Philipp}, title = {{The Complexity of Transitively Orienting Temporal Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {75:1--75:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.75}, URN = {urn:nbn:de:0030-drops-145157}, doi = {10.4230/LIPIcs.MFCS.2021.75}, annote = {Keywords: Temporal graph, transitive orientation, transitive closure, polynomial-time algorithm, NP-hardness, satisfiability} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Hendrik Molter, Malte Renken, and Philipp Zschoche. Temporal Reachability Minimization: Delaying vs. Deleting. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{molter_et_al:LIPIcs.MFCS.2021.76, author = {Molter, Hendrik and Renken, Malte and Zschoche, Philipp}, title = {{Temporal Reachability Minimization: Delaying vs. Deleting}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {76:1--76:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.76}, URN = {urn:nbn:de:0030-drops-145161}, doi = {10.4230/LIPIcs.MFCS.2021.76}, annote = {Keywords: Temporal Graphs, Temporal Paths, Disease Spreading, Network Flows, Parameterized Algorithms, NP-hard Problems} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Matthias Bentert, André Nichterlein, Malte Renken, and Philipp Zschoche. Using a Geometric Lens to Find k Disjoint Shortest Paths. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bentert_et_al:LIPIcs.ICALP.2021.26, author = {Bentert, Matthias and Nichterlein, Andr\'{e} and Renken, Malte and Zschoche, Philipp}, title = {{Using a Geometric Lens to Find k Disjoint Shortest Paths}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {26:1--26:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.26}, URN = {urn:nbn:de:0030-drops-140954}, doi = {10.4230/LIPIcs.ICALP.2021.26}, annote = {Keywords: graph algorithms, dynamic programming, W\lbrack1\rbrack-hardness, geometry} }
Feedback for Dagstuhl Publishing