Loading...
Loading...

Go to the content (press return)

Computing optimal shortcuts for networks

Author
Garijo, D.; Marquez, A.; Rodríguez, N.; Silveira, R.
Type of activity
Journal article
Journal
European journal of operational research
Date of publication
2019-11-16
Volume
279
Number
1
First page
26
Last page
37
DOI
10.1016/j.ejor.2019.05.018
Project funding
Geometry and graphs: interactions and applications
Repository
http://hdl.handle.net/2117/173524 Open in new window
https://arxiv.org/abs/1807.10093 Open in new window
URL
https://www.sciencedirect.com/science/article/abs/pii/S0377221719304229 Open in new window
Abstract
We study augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Problems of this type have received considerable attention recently, mostly for discrete variants of the problem. We consider a fully continuous setting, where the problem of computing distances and placing a shortcut is much harder as all points on the network, instead of only the vertices, must be taken into account. ...
Citation
Garijo, D. [et al.]. Computing optimal shortcuts for networks. "European journal of operational research", 16 Novembre 2019, vol. 279, núm. 1, p. 26-37.
Keywords
Complexity, Discrete optimization, Geometric algorithm, Graph augmentation, Networks
Group of research
CGA - Computational Geometry and Applications

Participants

  • Garijo Royo, Delia  (author)
  • Marquez Pérez, Alberto  (author)
  • Rodríguez, Natalia  (author)
  • Silveira, Rodrigo Ignacio  (author)