Algorithms for distance problems in continuous graphs

Cabello, Sergio (avtor), Garijo, Delia (avtor), Kalb, Antonia (avtor), Klute, Fabian (avtor), Parada, Irene (avtor), Silveira, Rodrigo I. (avtor)

We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with $m$ edges these values can be computed in roughly $O(m^2)$ time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most $k$ can be computed in $O(n \log^{O(k)} n)$ time, where $n$ is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with $n$ vertices and $F$ faces takes $O(n F \log n)$ time.

• Jezik: Angleški jezik
• Ključne besede: diameter, mean distance, continuous graphs, treewidth, planar graphs
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.08 - Objavljeni znanstveni prispevek na konferenci
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2025
• Št. strani: Str. 13:1-13:16
• PID: 20.500.12556/RUL-176952
• UDK: 004.42:519.17
• DOI: 10.4230/LIPIcs.WADS.2025.13
• COBISS.SI-ID: 261662723
• Datum objave v RUL: 16.12.2025

Gradivo je del monografije

• Naslov: 19th International Symposium on Algorithms and Data Structures : WADS 2025, August 11–15, 2025, York University, Toronto, Canada
• Uredniki: Pat Morin, Eunjin Oh
• Kraj izida: Saarbrücken/Wadern
• Založnik: Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
• Leto izida: 2025
• ISBN: 978-3-95977-398-0
• COBISS.SI-ID: 261608451
• Naslov zbirke: Leibniz international proceedings in informatics
• Številčenje v zbirki: ǂvol. ǂ349
• ISSN zbirke: 1868-8969

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.