Published in: LIPIcs, Volume 321, 19th International Symposium on Parameterized and Exact Computation (IPEC 2024)
Katrin Casel, Tobias Friedrich, Aikaterini Niklanovits, Kirill Simonov, and Ziena Zeif. Combining Crown Structures for Vulnerability Measures. In 19th International Symposium on Parameterized and Exact Computation (IPEC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 321, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{casel_et_al:LIPIcs.IPEC.2024.1, author = {Casel, Katrin and Friedrich, Tobias and Niklanovits, Aikaterini and Simonov, Kirill and Zeif, Ziena}, title = {{Combining Crown Structures for Vulnerability Measures}}, booktitle = {19th International Symposium on Parameterized and Exact Computation (IPEC 2024)}, pages = {1:1--1:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-353-9}, ISSN = {1868-8969}, year = {2024}, volume = {321}, editor = {Bonnet, \'{E}douard and Rz\k{a}\.{z}ewski, Pawe{\l}}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2024.1}, URN = {urn:nbn:de:0030-drops-222270}, doi = {10.4230/LIPIcs.IPEC.2024.1}, annote = {Keywords: Crown Decomposition, Kernelization, Vertex Integrity, Component Order Connectivity} }
Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells. How to Reduce Temporal Cliques to Find Sparse Spanners. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{angrick_et_al:LIPIcs.ESA.2024.11, author = {Angrick, Sebastian and Bals, Ben and Friedrich, Tobias and Gawendowicz, Hans and Hastrich, Niko and Klodt, Nicolas and Lenzner, Pascal and Schmidt, Jonas and Skretas, George and Wells, Armin}, title = {{How to Reduce Temporal Cliques to Find Sparse Spanners}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {11:1--11:15}, 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.11}, URN = {urn:nbn:de:0030-drops-210822}, doi = {10.4230/LIPIcs.ESA.2024.11}, annote = {Keywords: Temporal Graphs, temporal Clique, temporal Spanner, Reachability, Graph Connectivity, Graph Sparsification} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Janosch Ruff, and Ziena Zeif. On the Giant Component of Geometric Inhomogeneous Random Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 20:1-20:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blasius_et_al:LIPIcs.ESA.2023.20, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Ruff, Janosch and Zeif, Ziena}, title = {{On the Giant Component of Geometric Inhomogeneous Random Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {20:1--20:13}, 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.20}, URN = {urn:nbn:de:0030-drops-186737}, doi = {10.4230/LIPIcs.ESA.2023.20}, annote = {Keywords: geometric inhomogeneous random graphs, connectivity, giant component} }
Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{angrick_et_al:LIPIcs.SEA.2023.10, author = {Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo}, title = {{Solving Directed Feedback Vertex Set by Iterative Reduction to Vertex Cover}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.10}, URN = {urn:nbn:de:0030-drops-183602}, doi = {10.4230/LIPIcs.SEA.2023.10}, annote = {Keywords: directed feedback vertex set, vertex cover, reduction rules} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, Simon Krogmann, and Martin Schirneck. Fault-Tolerant ST-Diameter Oracles. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bilo_et_al:LIPIcs.ICALP.2023.24, author = {Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Krogmann, Simon and Schirneck, Martin}, title = {{Fault-Tolerant ST-Diameter Oracles}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {24:1--24:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.24}, URN = {urn:nbn:de:0030-drops-180762}, doi = {10.4230/LIPIcs.ICALP.2023.24}, annote = {Keywords: diameter oracles, distance sensitivity oracles, space lower bounds, fault-tolerant data structures} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Tobias Friedrich, Andreas Göbel, Maximilian Katzmann, and Leon Schiller. Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 62:1-62:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{friedrich_et_al:LIPIcs.ICALP.2023.62, author = {Friedrich, Tobias and G\"{o}bel, Andreas and Katzmann, Maximilian and Schiller, Leon}, title = {{Cliques in High-Dimensional Geometric Inhomogeneous Random Graphs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {62:1--62:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.62}, URN = {urn:nbn:de:0030-drops-181147}, doi = {10.4230/LIPIcs.ICALP.2023.62}, annote = {Keywords: random graphs, geometry, dimensionality, cliques, clique number, scale-free networks} }
Published in: LIPIcs, Volume 256, 4th Symposium on Foundations of Responsible Computing (FORC 2023)
Katrin Casel, Tobias Friedrich, Martin Schirneck, and Simon Wietheger. Fair Correlation Clustering in Forests. In 4th Symposium on Foundations of Responsible Computing (FORC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 256, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{casel_et_al:LIPIcs.FORC.2023.9, author = {Casel, Katrin and Friedrich, Tobias and Schirneck, Martin and Wietheger, Simon}, title = {{Fair Correlation Clustering in Forests}}, booktitle = {4th Symposium on Foundations of Responsible Computing (FORC 2023)}, pages = {9:1--9:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-272-3}, ISSN = {1868-8969}, year = {2023}, volume = {256}, editor = {Talwar, Kunal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2023.9}, URN = {urn:nbn:de:0030-drops-179307}, doi = {10.4230/LIPIcs.FORC.2023.9}, annote = {Keywords: correlation clustering, disparate impact, fair clustering, relaxed fairness} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, and Daniel Stephan. Strongly Hyperbolic Unit Disk Graphs. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blasius_et_al:LIPIcs.STACS.2023.13, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Stephan, Daniel}, title = {{Strongly Hyperbolic Unit Disk Graphs}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {13:1--13:17}, 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.13}, URN = {urn:nbn:de:0030-drops-176652}, doi = {10.4230/LIPIcs.STACS.2023.13}, annote = {Keywords: hyperbolic geometry, unit disk graphs, greedy routing, hyperbolic random graphs, graph classes} }
Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Sebastian Angrick, Ben Bals, Katrin Casel, Sarel Cohen, Tobias Friedrich, Niko Hastrich, Theresa Hradilak, Davis Issac, Otto Kißig, Jonas Schmidt, and Leo Wendt. PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 28:1-28:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{angrick_et_al:LIPIcs.IPEC.2022.28, author = {Angrick, Sebastian and Bals, Ben and Casel, Katrin and Cohen, Sarel and Friedrich, Tobias and Hastrich, Niko and Hradilak, Theresa and Issac, Davis and Ki{\ss}ig, Otto and Schmidt, Jonas and Wendt, Leo}, title = {{PACE Solver Description: Mount Doom - An Exact Solver for Directed Feedback Vertex Set}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {28:1--28:4}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.28}, URN = {urn:nbn:de:0030-drops-173847}, doi = {10.4230/LIPIcs.IPEC.2022.28}, annote = {Keywords: directed feedback vertex set, vertex cover, reduction rules} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Tobias Friedrich, Davis Issac, Nikhil Kumar, Nadym Mallek, and Ziena Zeif. A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{friedrich_et_al:LIPIcs.APPROX/RANDOM.2022.55, author = {Friedrich, Tobias and Issac, Davis and Kumar, Nikhil and Mallek, Nadym and Zeif, Ziena}, title = {{A Primal-Dual Algorithm for Multicommodity Flows and Multicuts in Treewidth-2 Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {55:1--55:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.55}, URN = {urn:nbn:de:0030-drops-171774}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.55}, annote = {Keywords: Approximation Algorithms, Multicommodity Flow, Multicut} }
Published in: Dagstuhl Reports, Volume 12, Issue 2 (2022)
Anne Auger, Carlos M. Fonseca, Tobias Friedrich, Johannes Lengler, and Armand Gissler. Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081). In Dagstuhl Reports, Volume 12, Issue 2, pp. 87-102, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@Article{auger_et_al:DagRep.12.2.87, author = {Auger, Anne and Fonseca, Carlos M. and Friedrich, Tobias and Lengler, Johannes and Gissler, Armand}, title = {{Theory of Randomized Optimization Heuristics (Dagstuhl Seminar 22081)}}, pages = {87--102}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2022}, volume = {12}, number = {2}, editor = {Auger, Anne and Fonseca, Carlos M. and Friedrich, Tobias and Lengler, Johannes and Gissler, Armand}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.2.87}, URN = {urn:nbn:de:0030-drops-169325}, doi = {10.4230/DagRep.12.2.87}, annote = {Keywords: black-box optimization, derivative-free optimization, evolutionary and genetic algorithms, randomized search algorithms, stochastic gradient descent, theoretical computer science} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Davide Bilò, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 22:1-22:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bilo_et_al:LIPIcs.ICALP.2022.22, author = {Bil\`{o}, Davide and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, title = {{Deterministic Sensitivity Oracles for Diameter, Eccentricities and All Pairs Distances}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {22:1--22:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.22}, URN = {urn:nbn:de:0030-drops-163633}, doi = {10.4230/LIPIcs.ICALP.2022.22}, annote = {Keywords: derandomization, diameter, eccentricity, fault-tolerant data structure, sensitivity oracle, space lower bound} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Tobias Friedrich, Hans Gawendowicz, Pascal Lenzner, and Anna Melnichenko. Social Distancing Network Creation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 62:1-62:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{friedrich_et_al:LIPIcs.ICALP.2022.62, author = {Friedrich, Tobias and Gawendowicz, Hans and Lenzner, Pascal and Melnichenko, Anna}, title = {{Social Distancing Network Creation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {62:1--62:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.62}, URN = {urn:nbn:de:0030-drops-164038}, doi = {10.4230/LIPIcs.ICALP.2022.62}, annote = {Keywords: Algorithmic Game Theory, Equilibrium Existence, Price of Anarchy, Network Creation Game, Social Distancing, Maximization vs. Minimization Problems} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Davide Bilò, Katrin Casel, Keerti Choudhary, Sarel Cohen, Tobias Friedrich, J.A. Gregor Lagodzinski, Martin Schirneck, and Simon Wietheger. Fixed-Parameter Sensitivity Oracles. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bilo_et_al:LIPIcs.ITCS.2022.23, author = {Bil\`{o}, Davide and Casel, Katrin and Choudhary, Keerti and Cohen, Sarel and Friedrich, Tobias and Lagodzinski, J.A. Gregor and Schirneck, Martin and Wietheger, Simon}, title = {{Fixed-Parameter Sensitivity Oracles}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {23:1--23:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.23}, URN = {urn:nbn:de:0030-drops-156196}, doi = {10.4230/LIPIcs.ITCS.2022.23}, annote = {Keywords: data structures, distance preservers, distance sensitivity oracles, fault tolerance, fixed-parameter tractability, k-path, vertex cover} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Thomas Bläsius, Tobias Friedrich, Martin S. Krejca, and Louise Molitor. The Impact of Geometry on Monochrome Regions in the Flip Schelling Process. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasius_et_al:LIPIcs.ISAAC.2021.29, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Krejca, Martin S. and Molitor, Louise}, title = {{The Impact of Geometry on Monochrome Regions in the Flip Schelling Process}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {29:1--29: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.29}, URN = {urn:nbn:de:0030-drops-154623}, doi = {10.4230/LIPIcs.ISAAC.2021.29}, annote = {Keywords: Agent-based Model, Schelling Segregation, Spin System} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bilo_et_al:LIPIcs.ESA.2021.18, author = {Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, title = {{Near-Optimal Deterministic Single-Source Distance Sensitivity Oracles}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {18:1--18: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.18}, URN = {urn:nbn:de:0030-drops-145999}, doi = {10.4230/LIPIcs.ESA.2021.18}, annote = {Keywords: derandomization, distance sensitivity oracle, single-source replacement paths, space lower bound} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 20:1-20:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasius_et_al:LIPIcs.ESA.2021.20, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian}, title = {{Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {20:1--20:15}, 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.20}, URN = {urn:nbn:de:0030-drops-146012}, doi = {10.4230/LIPIcs.ESA.2021.20}, annote = {Keywords: vertex cover, approximation, random graphs, hyperbolic geometry, efficient algorithm} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Thomas Bläsius, Tobias Friedrich, and Christopher Weyand. Efficiently Computing Maximum Flows in Scale-Free Networks. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasius_et_al:LIPIcs.ESA.2021.21, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Weyand, Christopher}, title = {{Efficiently Computing Maximum Flows in Scale-Free Networks}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {21:1--21:14}, 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.21}, URN = {urn:nbn:de:0030-drops-146029}, doi = {10.4230/LIPIcs.ESA.2021.21}, annote = {Keywords: graphs, flow, network, scale-free} }
Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)
Katrin Casel, Tobias Friedrich, Davis Issac, Aikaterini Niklanovits, and Ziena Zeif. Balanced Crown Decomposition for Connectivity Constraints. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{casel_et_al:LIPIcs.ESA.2021.26, author = {Casel, Katrin and Friedrich, Tobias and Issac, Davis and Niklanovits, Aikaterini and Zeif, Ziena}, title = {{Balanced Crown Decomposition for Connectivity Constraints}}, booktitle = {29th Annual European Symposium on Algorithms (ESA 2021)}, pages = {26:1--26:15}, 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.26}, URN = {urn:nbn:de:0030-drops-146076}, doi = {10.4230/LIPIcs.ESA.2021.26}, annote = {Keywords: crown decomposition, connected partition, balanced partition, approximation algorithms} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Davide Bilò, Sarel Cohen, Tobias Friedrich, and Martin Schirneck. Space-Efficient Fault-Tolerant Diameter Oracles. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bilo_et_al:LIPIcs.MFCS.2021.18, author = {Bil\`{o}, Davide and Cohen, Sarel and Friedrich, Tobias and Schirneck, Martin}, title = {{Space-Efficient Fault-Tolerant Diameter Oracles}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {18:1--18:16}, 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.18}, URN = {urn:nbn:de:0030-drops-144581}, doi = {10.4230/LIPIcs.MFCS.2021.18}, annote = {Keywords: derandomization, diameter, distance sensitivity oracle, fault-tolerant data structure, space lower bound} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Tobias Friedrich, Andreas Göbel, Martin S. Krejca, and Marcus Pappik. A Spectral Independence View on Hard Spheres via Block Dynamics. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 66:1-66:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{friedrich_et_al:LIPIcs.ICALP.2021.66, author = {Friedrich, Tobias and G\"{o}bel, Andreas and Krejca, Martin S. and Pappik, Marcus}, title = {{A Spectral Independence View on Hard Spheres via Block Dynamics}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {66:1--66:15}, 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.66}, URN = {urn:nbn:de:0030-drops-141353}, doi = {10.4230/LIPIcs.ICALP.2021.66}, annote = {Keywords: Hard-sphere Model, Markov Chain, Partition Function, Gibbs Distribution, Approximate Counting, Spectral Independence} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
J. A. Gregor Lagodzinski, Andreas Göbel, Katrin Casel, and Tobias Friedrich. On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 91:1-91:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{lagodzinski_et_al:LIPIcs.ICALP.2021.91, author = {Lagodzinski, J. A. Gregor and G\"{o}bel, Andreas and Casel, Katrin and Friedrich, Tobias}, title = {{On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {91:1--91:15}, 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.91}, URN = {urn:nbn:de:0030-drops-141608}, doi = {10.4230/LIPIcs.ICALP.2021.91}, annote = {Keywords: Algorithms, Theory, Quantum Graphs, Bipartite Graphs, Graph Homomorphisms, Modular Counting, Complexity Dichotomy} }
Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)
Thomas Bläsius, Tobias Friedrich, and Maximilian Katzmann. Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasius_et_al:LIPIcs.SEA.2021.22, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian}, title = {{Force-Directed Embedding of Scale-Free Networks in the Hyperbolic Plane}}, booktitle = {19th International Symposium on Experimental Algorithms (SEA 2021)}, pages = {22:1--22:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-185-6}, ISSN = {1868-8969}, year = {2021}, volume = {190}, editor = {Coudert, David and Natale, Emanuele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.22}, URN = {urn:nbn:de:0030-drops-137944}, doi = {10.4230/LIPIcs.SEA.2021.22}, annote = {Keywords: force-directed drawing algorithms, spring embedding, hyperbolic space} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Davide Bilò, Tobias Friedrich, Pascal Lenzner, Anna Melnichenko, and Louise Molitor. Fair Tree Connection Games with Topology-Dependent Edge Cost. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{bilo_et_al:LIPIcs.FSTTCS.2020.15, author = {Bil\`{o}, Davide and Friedrich, Tobias and Lenzner, Pascal and Melnichenko, Anna and Molitor, Louise}, title = {{Fair Tree Connection Games with Topology-Dependent Edge Cost}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.15}, URN = {urn:nbn:de:0030-drops-132562}, doi = {10.4230/LIPIcs.FSTTCS.2020.15}, annote = {Keywords: Network Design Games, Spanning Tree Games, Fair Cost Sharing, Price of Anarchy, Nash Equilibrium, Algorithmic Game Theory, Combinatorics} }
Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)
Thomas Bläsius, Maximilian Böther, Philipp Fischbeck, Tobias Friedrich, Alina Gries, Falk Hüffner, Otto Kißig, Pascal Lenzner, Louise Molitor, Leon Schiller, Armin Wells, and Simon Wietheger. A Strategic Routing Framework and Algorithms for Computing Alternative Paths. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blasius_et_al:OASIcs.ATMOS.2020.10, author = {Bl\"{a}sius, Thomas and B\"{o}ther, Maximilian and Fischbeck, Philipp and Friedrich, Tobias and Gries, Alina and H\"{u}ffner, Falk and Ki{\ss}ig, Otto and Lenzner, Pascal and Molitor, Louise and Schiller, Leon and Wells, Armin and Wietheger, Simon}, title = {{A Strategic Routing Framework and Algorithms for Computing Alternative Paths}}, booktitle = {20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)}, pages = {10:1--10:14}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-170-2}, ISSN = {2190-6807}, year = {2020}, volume = {85}, editor = {Huisman, Dennis and Zaroliagis, Christos D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.10}, URN = {urn:nbn:de:0030-drops-131469}, doi = {10.4230/OASIcs.ATMOS.2020.10}, annote = {Keywords: Routing, Strategic Routing, Selfish Routing, Route Planning, Network Flow, Algorithm Design} }
Published in: LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020)
Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Minimization of Random Hypergraphs. In 28th Annual European Symposium on Algorithms (ESA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 173, pp. 21:1-21:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blasius_et_al:LIPIcs.ESA.2020.21, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin}, title = {{The Minimization of Random Hypergraphs}}, booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)}, pages = {21:1--21:15}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.21}, URN = {urn:nbn:de:0030-drops-128871}, doi = {10.4230/LIPIcs.ESA.2020.21}, annote = {Keywords: Chernoff-Hoeffding theorem, maximum entropy, maximization, minimization, phase transition, random hypergraphs} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Thomas Bläsius, Philipp Fischbeck, Tobias Friedrich, and Maximilian Katzmann. Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blasius_et_al:LIPIcs.STACS.2020.25, author = {Bl\"{a}sius, Thomas and Fischbeck, Philipp and Friedrich, Tobias and Katzmann, Maximilian}, title = {{Solving Vertex Cover in Polynomial Time on Hyperbolic Random Graphs}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {25:1--25: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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.25}, URN = {urn:nbn:de:0030-drops-118865}, doi = {10.4230/LIPIcs.STACS.2020.25}, annote = {Keywords: vertex cover, random graphs, hyperbolic geometry, efficient algorithm} }
Published in: Dagstuhl Reports, Volume 9, Issue 10 (2020)
Carola Doerr, Carlos M. Fonseca, Tobias Friedrich, and Xin Yao. Theory of Randomized Optimization Heuristics (Dagstuhl Reports 19431). In Dagstuhl Reports, Volume 9, Issue 10, pp. 61-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@Article{doerr_et_al:DagRep.9.10.61, author = {Doerr, Carola and Fonseca, Carlos M. and Friedrich, Tobias and Yao, Xin}, title = {{Theory of Randomized Optimization Heuristics (Dagstuhl Reports 19431)}}, pages = {61--94}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2020}, volume = {9}, number = {10}, editor = {Doerr, Carola and Fonseca, Carlos M. and Friedrich, Tobias and Yao, Xin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.10.61}, URN = {urn:nbn:de:0030-drops-118567}, doi = {10.4230/DagRep.9.10.61}, annote = {Keywords: algorithms and complexity, evolutionary algorithms, machine learning, optimization, soft computing} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann, Ulrich Meyer, Manuel Penschuck, and Christopher Weyand. Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 21:1-21:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{blasius_et_al:LIPIcs.ESA.2019.21, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Katzmann, Maximilian and Meyer, Ulrich and Penschuck, Manuel and Weyand, Christopher}, title = {{Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {21:1--21:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.21}, URN = {urn:nbn:de:0030-drops-111424}, doi = {10.4230/LIPIcs.ESA.2019.21}, annote = {Keywords: hyperbolic random graphs, geometric inhomogeneous random graph, efficient network generation} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Tobias Friedrich and Ralf Rothenberger. The Satisfiability Threshold for Non-Uniform Random 2-SAT. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 61:1-61:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{friedrich_et_al:LIPIcs.ICALP.2019.61, author = {Friedrich, Tobias and Rothenberger, Ralf}, title = {{The Satisfiability Threshold for Non-Uniform Random 2-SAT}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {61:1--61:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.61}, URN = {urn:nbn:de:0030-drops-106372}, doi = {10.4230/LIPIcs.ICALP.2019.61}, annote = {Keywords: random SAT, satisfiability threshold, sharpness, non-uniform distribution, 2-SAT} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Tobias Friedrich. From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity (Tutorial). In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 5:1-5:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{friedrich:LIPIcs.STACS.2019.5, author = {Friedrich, Tobias}, title = {{From Graph Theory to Network Science: The Natural Emergence of Hyperbolicity}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {5:1--5:9}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.5}, URN = {urn:nbn:de:0030-drops-102445}, doi = {10.4230/LIPIcs.STACS.2019.5}, annote = {Keywords: Graph Theory, Graph Algorithms, Network Science, Hyperbolic Geometry} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, and Marianne Thieffry. Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{blasius_et_al:LIPIcs.ICALP.2018.20, author = {Bl\"{a}sius, Thomas and Freiberger, Cedric and Friedrich, Tobias and Katzmann, Maximilian and Montenegro-Retana, Felix and Thieffry, Marianne}, title = {{Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.20}, URN = {urn:nbn:de:0030-drops-90246}, doi = {10.4230/LIPIcs.ICALP.2018.20}, annote = {Keywords: random graphs, hyperbolic geometry, scale-free networks, bidirectional shortest path} }
Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)
Tobias Friedrich, Anton Krohmer, Ralf Rothenberger, Thomas Sauerwald, and Andrew M. Sutton. Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{friedrich_et_al:LIPIcs.ESA.2017.37, author = {Friedrich, Tobias and Krohmer, Anton and Rothenberger, Ralf and Sauerwald, Thomas and Sutton, Andrew M.}, title = {{Bounds on the Satisfiability Threshold for Power Law Distributed Random SAT}}, booktitle = {25th Annual European Symposium on Algorithms (ESA 2017)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-049-1}, ISSN = {1868-8969}, year = {2017}, volume = {87}, editor = {Pruhs, Kirk and Sohler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.37}, URN = {urn:nbn:de:0030-drops-78356}, doi = {10.4230/LIPIcs.ESA.2017.37}, annote = {Keywords: satisfiability, random structures, random SAT, power law distribution, scale-freeness, phase transitions} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Thomas Bläsius, Tobias Friedrich, and Martin Schirneck. The Parameterized Complexity of Dependency Detection in Relational Databases. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blasius_et_al:LIPIcs.IPEC.2016.6, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Schirneck, Martin}, title = {{The Parameterized Complexity of Dependency Detection in Relational Databases}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.6}, URN = {urn:nbn:de:0030-drops-69202}, doi = {10.4230/LIPIcs.IPEC.2016.6}, annote = {Keywords: parameterized complexity, unique column combination, functional dependency, inclusion dependency, profiling relational data} }
Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)
Ankit Chauhan, Tobias Friedrich, and Ralf Rothenberger. Greed is Good for Deterministic Scale-Free Networks. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{chauhan_et_al:LIPIcs.FSTTCS.2016.33, author = {Chauhan, Ankit and Friedrich, Tobias and Rothenberger, Ralf}, title = {{Greed is Good for Deterministic Scale-Free Networks}}, booktitle = {36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)}, pages = {33:1--33:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-027-9}, ISSN = {1868-8969}, year = {2016}, volume = {65}, editor = {Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.33}, URN = {urn:nbn:de:0030-drops-68682}, doi = {10.4230/LIPIcs.FSTTCS.2016.33}, annote = {Keywords: random graphs, power-law degree distribution, scale-free networks, PLB networks, approximation algorithms, vertex cover, dominating set, independent s} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Tobias Friedrich. Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms (Invited Talk). In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 4:1-4:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{friedrich:LIPIcs.MFCS.2016.4, author = {Friedrich, Tobias}, title = {{Scale-Free Networks, Hyperbolic Geometry, and Efficient Algorithms}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {4:1--4:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.4}, URN = {urn:nbn:de:0030-drops-65106}, doi = {10.4230/LIPIcs.MFCS.2016.4}, annote = {Keywords: power-law graphs, scale-free graphs, random graphs, distributed algorithms} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Tobias Arndt, Danijar Hafner, Thomas Kellermeier, Simon Krogmann, Armin Razmjou, Martin S. Krejca, Ralf Rothenberger, and Tobias Friedrich. Probabilistic Routing for On-Street Parking Search. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{arndt_et_al:LIPIcs.ESA.2016.6, author = {Arndt, Tobias and Hafner, Danijar and Kellermeier, Thomas and Krogmann, Simon and Razmjou, Armin and Krejca, Martin S. and Rothenberger, Ralf and Friedrich, Tobias}, title = {{Probabilistic Routing for On-Street Parking Search}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.6}, URN = {urn:nbn:de:0030-drops-63489}, doi = {10.4230/LIPIcs.ESA.2016.6}, annote = {Keywords: parking search, on-street parking, probabilistic routing, constrained optimization, dataset} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Thomas Bläsius, Tobias Friedrich, and Anton Krohmer. Hyperbolic Random Graphs: Separators and Treewidth. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{blasius_et_al:LIPIcs.ESA.2016.15, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Krohmer, Anton}, title = {{Hyperbolic Random Graphs: Separators and Treewidth}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {15:1--15:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.15}, URN = {urn:nbn:de:0030-drops-63667}, doi = {10.4230/LIPIcs.ESA.2016.15}, annote = {Keywords: hyperbolic random graphs, scale-free networks, power-law graphs, separators, treewidth} }
Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)
Thomas Bläsius, Tobias Friedrich, Anton Krohmer, and Sören Laue. Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{blasius_et_al:LIPIcs.ESA.2016.16, author = {Bl\"{a}sius, Thomas and Friedrich, Tobias and Krohmer, Anton and Laue, S\"{o}ren}, title = {{Efficient Embedding of Scale-Free Graphs in the Hyperbolic Plane}}, booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)}, pages = {16:1--16:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-015-6}, ISSN = {1868-8969}, year = {2016}, volume = {57}, editor = {Sankowski, Piotr and Zaroliagis, Christos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.16}, URN = {urn:nbn:de:0030-drops-63670}, doi = {10.4230/LIPIcs.ESA.2016.16}, annote = {Keywords: hyperbolic random graphs, embedding, power-law graphs, hyperbolic plane} }
Feedback for Dagstuhl Publishing