dc.creator | Garijo Royo, Delia | es |
dc.creator | Márquez Pérez, Alberto | es |
dc.creator | Silveira, Rodrigo I. | es |
dc.date.accessioned | 2021-06-14T09:25:40Z | |
dc.date.available | 2021-06-14T09:25:40Z | |
dc.date.issued | 2021 | |
dc.identifier.citation | Garijo Royo, D., Márquez Pérez, A. y Silveira, R.I. (2021). Continuous mean distance of a weighted graph. ArXiv.org, arXiv:2103.11676 | |
dc.identifier.uri | https://hdl.handle.net/11441/111758 | |
dc.description.abstract | We study the concept of the continuous mean distance of a weighted graph. For
connected unweighted graphs, the mean distance can be de ned 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 in nite number of distances, something that increases the di culty
of the parameter.
In this paper we show that the continuous mean distance of a weighted graph can
be computed in time quadratic in the number of edges, by two di erent methods that
apply fundamental concepts in discrete algorithms and computational geometry. We also
present structural results that allow 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 the convergence when iteratively subdividing the edges of the weighted graph. | es |
dc.description.sponsorship | Ministerio de Ciencia e Innnovación PID2019-104129GB-I00/AEI/10.13039/501100011033 | es |
dc.description.sponsorship | Ministerio de Economía y Competitividad BFU2016-74975-P | es |
dc.format | application/pdf | es |
dc.format.extent | 27 | es |
dc.language.iso | eng | es |
dc.publisher | Cornell University | es |
dc.relation.ispartof | ArXiv.org, arXiv:2103.11676 | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.title | Continuous mean distance of a weighted graph | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/publishedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) | es |
dc.relation.projectID | PID2019-104129GB-I00/AEI/10.13039/501100011033 | es |
dc.relation.projectID | BFU2016-74975-P | es |
dc.relation.publisherversion | https://arxiv.org/abs/2103.11676 | es |
dc.journaltitle | ArXiv.org | es |
dc.publication.issue | arXiv:2103.11676 | es |
dc.contributor.funder | Ministerio de Ciencia e Innovación (MICIN). España | es |
dc.contributor.funder | Ministerio de Economía y Competitividad (MINECO). España | es |