Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Kostas Lakis, Johannes Lengler, Kalina Petrova, and Leon Schiller. Improved Bounds for Graph Distances in Scale Free Percolation and Related Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 74:1-74:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{lakis_et_al:LIPIcs.APPROX/RANDOM.2024.74, author = {Lakis, Kostas and Lengler, Johannes and Petrova, Kalina and Schiller, Leon}, title = {{Improved Bounds for Graph Distances in Scale Free Percolation and Related Models}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {74:1--74:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.74}, URN = {urn:nbn:de:0030-drops-210676}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.74}, annote = {Keywords: Mathematics, Probability Theory, Combinatorics, Random Graphs, Random Metric Spaces} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, and Kasper Green Larsen. Sublinear Time Shortest Path in Expander Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{alon_et_al:LIPIcs.MFCS.2024.8, author = {Alon, Noga and Gr{\o}nlund, Allan and J{\o}rgensen, S{\o}ren Fuglede and Larsen, Kasper Green}, title = {{Sublinear Time Shortest Path in Expander Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {8:1--8:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.8}, URN = {urn:nbn:de:0030-drops-205646}, doi = {10.4230/LIPIcs.MFCS.2024.8}, annote = {Keywords: Shortest Path, Expanders, Breadth First Search, Graph Algorithms} }
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)
Thomas Bläsius, Maximilian Katzmann, and Marcus Wilhelm. Partitioning the Bags of a Tree Decomposition into Cliques. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blasius_et_al:LIPIcs.SEA.2023.3, author = {Bl\"{a}sius, Thomas and Katzmann, Maximilian and Wilhelm, Marcus}, title = {{Partitioning the Bags of a Tree Decomposition into Cliques}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {3:1--3:19}, 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.3}, URN = {urn:nbn:de:0030-drops-183533}, doi = {10.4230/LIPIcs.SEA.2023.3}, annote = {Keywords: treewidth, weighted treewidth, algorithm engineering, cliques, clustering, complex networks} }
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 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 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 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 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: 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 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} }
Feedback for Dagstuhl Publishing