Artículo
Shortcut sets for the locus of plane Euclidean networks
Autor/es | Cáceres, José
Garijo Royo, Delia González, Antonio Márquez Pérez, Alberto Puertas, María Luz Ribeiro, Paula |
Departamento | Universidad de Sevilla. Departamento de Matemática Aplicada I (ETSII) |
Fecha de publicación | 2018 |
Fecha de depósito | 2020-06-21 |
Publicado en |
|
Resumen | We study the problem of augmenting the locus N of a plane Euclidean network N by in- serting iteratively a finite set of segments, called shortcut set , while reducing the diameterof the locus of the resulting network. ... We study the problem of augmenting the locus N of a plane Euclidean network N by in- serting iteratively a finite set of segments, called shortcut set , while reducing the diameterof the locus of the resulting network. There are two main differences with the classicalaugmentation problems: the endpoints of the segments are allowed to be points of N as well as points of the previously inserted segments (instead of only vertices of N ), and the notion of diameter is adapted to the fact that we deal with N instead of N . This increases enormously the hardness of the problem but also its possible practical applications to net- work design. Among other results, we characterize the existence of shortcut sets, computethem in polynomial time, and analyze the role of the convex hull of N when inserting a shortcut set. Our main results prove that, while the problem of minimizing the size of ashortcut set is NP-hard, one can always determine in polynomial time whether insertingonly one segment suffices to reduce the diameter. |
Agencias financiadoras | Ministerio de Economía y Competitividad (MINECO). España |
Identificador del proyecto | MTM2015-63791-R |
Cita | Cáceres, J., Garijo Royo, D., González, A., Márquez Pérez, A., Puertas, M.L. y Ribeiro, P. (2018). Shortcut sets for the locus of plane Euclidean networks. Applied Mathematics and Computation, 334 (october 2018), 192-205. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
Shortcut sets for the locus of ... | 689.1Kb | [PDF] | Ver/ | |