• Continuous mean distance of a...

Treffer: Continuous mean distance of a weighted graph

Title:
Continuous mean distance of a weighted graph
Authors:
Garijo Royo, Delia, Marquez Pérez, Alberto, Silveira, Rodrigo Ignacio
Contributors:
Universitat Politècnica de Catalunya. Departament de Matemàtiques, Universitat Politècnica de Catalunya. DCCG - Discrete, Combinational, and Computational Geometry
Publication Year:
2022
Collection:
Universitat Politècnica de Catalunya, BarcelonaTech: UPCommons - Global access to UPC knowledge
Subject Terms:
Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria computacional, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs, Àrees temàtiques de la UPC::Matemàtiques i estadística::Geometria::Geometria algebraica, Numerical analysis, Graph theory, Geometry, Algebraic, Anàlisi numèrica, Grafs, Teoria de, Geometria algebraica, Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Classificació AMS::05 Combinatorics::05C Graph theory, Classificació AMS::14 Algebraic geometry::14Q Computational aspects in algebraic geometry
Document Type:
Konferenz conference object
File Description:
application/pdf
Language:
English
Relation:
info:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-104129GB-I00/ES/TEORIA Y APLICACIONES DE CONFIGURACIONES DE PUNTOS Y REDES/; https://arxiv.org/abs/2103.11676; http://hdl.handle.net/2117/384982
Availability:
http://hdl.handle.net/2117/384982
https://arxiv.org/abs/2103.11676
Rights:
Open Access
Accession Number:
edsbas.42C2FD73
Database:
BASE

Weitere Informationen

We study the concept of the continuous mean distance of a weighted graph. For connected unweighted graphs, the mean distance can be defined as the arithmetic mean of the distances between all pairs of vertices. This parameter provides a natural measure of the compactness of the graph, and has been intensively studied, together with several variants, including its version for weighted graphs. The continuous analog of the (discrete) mean distance is the mean of the distances between all pairs of points on the edges of the graph. Despite being a very natural generalization, to the best of our knowledge this concept has been barely studied, since the jump from discrete to continuous implies having to deal with an infinite number of distances, something that increases the difficulty of the parameter. In this paper, we show that the continuous mean distance of a weighted graph can be computed in time roughly quadratic in the number of edges, by two different methods that apply fundamental concepts in discrete algorithms and computational geometry. We also present structural results that allow for a faster computation of this continuous parameter for several classes of weighted graphs. Finally, we study the relation between the (discrete) mean distance and its continuous counterpart, mainly focusing on the relevant question of convergence when iteratively subdividing the edges of the weighted graph. ; This work was supported by grants PID2019-104129GB-I00/ AEI/ 10.13039/501100011033, Gen. Cat. 2017SGR1640, and PID2019-103900GB-I00. ; Peer Reviewed ; Postprint (author's final draft)