Search Results

Documents authored by Proissl, Claudius

Document
DOI: 10.4230/LIPIcs.SEA.2025.17
Computing the Exact Radius of Large Graphs

Authors: Stefan Funke, Claudius Proissl, and Sabine Storandt

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
The radius of a graph is an important structural parameter which plays a key role in social network analysis and related applications. It measures the minimum shortest path distance that is required to reach all nodes in the graph from a single node. A node from which all other nodes are within a distance equal to the radius is called a center of the graph. In a graph with n nodes and m edges, the center and the radius can be determined in Õ(nm) by computing shortest path distances between all pairs of nodes. Fine-grained complexity results suggest that asymptotically faster algorithms are unlikely to exist. In this paper, we describe a novel randomized algorithm for exact radius computation in weighted digraphs with an expected running time in Õ(d³m) where d is the so-called combinatorial dimension. Our methodology is inspired by Clarkson’s algorithm for LP-type problems. The value of d denotes the size of a basis, which is a smallest subset of nodes which enforce the same radius as the whole node set. While we show that there exist graphs with d ∈ Θ(n), our empirical analysis reveals that even large real-world graphs have small combinatorial dimension. This allows us to compute the radius in near-linear time on such instances. The significantly improved scalability can be clearly observed in our experimental evaluation on a diverse set of benchmark graphs.
Cite as

Stefan Funke, Claudius Proissl, and Sabine Storandt. Computing the Exact Radius of Large Graphs. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{funke_et_al:LIPIcs.SEA.2025.17,
  author =	{Funke, Stefan and Proissl, Claudius and Storandt, Sabine},
  title =	{{Computing the Exact Radius of Large Graphs}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{17:1--17:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.17},
  URN =		{urn:nbn:de:0030-drops-232555},
  doi =		{10.4230/LIPIcs.SEA.2025.17},
  annote =	{Keywords: Radius, Graph Center, LP-type, Combinatorial Dimension}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.14
An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions

Authors: Florian Barth, Stefan Funke, and Claudius Proissl

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Graphs with multiple edge costs arise naturally in the route planning domain when apart from travel time other criteria like fuel consumption or positive height difference are also objectives to be minimized. In such a scenario, this paper investigates the number of extreme shortest paths between a given source-target pair s, t. We show that for a fixed but arbitrary number of cost types d ≥ 1 the number of extreme shortest paths is in n^O(log^{d-1}n) in graphs G with n nodes. This is a generalization of known upper bounds for d = 2 and d = 3.
Cite as

Florian Barth, Stefan Funke, and Claudius Proissl. An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 14:1-14:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.ESA.2022.14,
  author =	{Barth, Florian and Funke, Stefan and Proissl, Claudius},
  title =	{{An Upper Bound on the Number of Extreme Shortest Paths in Arbitrary Dimensions}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{14:1--14:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.14},
  URN =		{urn:nbn:de:0030-drops-169525},
  doi =		{10.4230/LIPIcs.ESA.2022.14},
  annote =	{Keywords: Parametric Shortest Paths, Extreme Shortest Paths}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.15
Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets

Authors: Florian Barth, Stefan Funke, and Claudius Proissl

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
In a road network with multicriteria edge costs we consider the problem of computing a minimum number of driving preferences such that a given set of paths/trajectories is optimal under at least one of these preferences. While the exact formulation and solution of this problem appears theoretically hard, we show that in practice one can solve the problem exactly even for non-homeopathic instance sizes of several thousand trajectories in a road network of several million nodes. We also present a parameterized guaranteed-polynomial-time scheme with very good practical performance.
Cite as

Florian Barth, Stefan Funke, and Claudius Proissl. Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{barth_et_al:LIPIcs.ISAAC.2021.15,
  author =	{Barth, Florian and Funke, Stefan and Proissl, Claudius},
  title =	{{Preference-Based Trajectory Clustering - An Application of Geometric Hitting Sets}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{15:1--15:14},
  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.15},
  URN =		{urn:nbn:de:0030-drops-154481},
  doi =		{10.4230/LIPIcs.ISAAC.2021.15},
  annote =	{Keywords: Route planning, personalization, computational geometry}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact