2026-04-05T13:11:45Zhttps://recercat.cat/oai/request

oai:recercat.cat:2117/1735242026-01-30T07:21:41Zcom_2072_1033col_2072_452950

Computing optimal shortcuts for networks Garijo Royo, Delia Marquez Pérez, Alberto Rodríguez, Natalia Silveira, Rodrigo Ignacio Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica Geometry, Algebraic Programming (Mathematics) Networks Geometric algorithm Complexity Discrete optimization Graph augmentation Geometria algèbrica Programació (Matemàtica) Classificació AMS::14 Algebraic geometry::14Q Computational aspects in algebraic geometry Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming 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. We present the first results on the computation of optimal shortcuts for general networks in this model: a polynomial time algorithm and a discretization of the problem that leads to an approximation algorithm. We also improve the general method for networks that are paths, restricted to two types of shortcuts: those with a fixed orientation and simple shortcuts. Peer Reviewed Postprint (author's final draft) 2019-11-16 Article https://www.sciencedirect.com/science/article/abs/pii/S0377221719304229 info:eu-repo/grantAgreement/MINECO//MTM2015-63791-R/ES/GRAFOS Y GEOMETRIA: INTERACCIONES Y APLICACIONES/ Open Access Elsevier