<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

Computing optimal shortcuts for networks

Name: Computing optimal shortcuts for networks
Keywords: Geometric algorithm, Computational Geometry (cs.CG), FOS: Computer and information sciences, geometric graph, :Matemàtiques i estadística::Investigació operativa::Programació matemàtica [Àrees temàtiques de la UPC], mathematical programming::90C Mathematical programming, graph augmentation, Geometry, shortcut, :Matemàtiques i estadística::Matemàtica aplicada a les ciències [Àrees temàtiques de la UPC]

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Conference object 01 Nov 2019Embargo end date: 01 Jan 2018 Spain, Spain, Spain, Germany Publisher:Elsevier BVJournal:European Journal of Operational Research, volume 279, pages 26-37 (issn: 0377-2217,

Authors: Garijo Royo, Delia; Marquez Pérez, Alberto; Rodríguez, Natalia; Silveira, Rodrigo Ignacio;

doi: 10.1016/j.ejor.2019.05.018 , 10.48550/arxiv.1807.10093

arXiv: http://arxiv.org/abs/1807.10093

handle: 2117/127293 , 2117/173524 , 2117/127292

Computing optimal shortcuts for networks

- Summary
- Subjects
- Metrics

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. 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.

21 pages

Countries

Spain, Spain, Spain, Germany

Related Organizations

Leibniz Association
Germany
Universitat Politècnica de Catalunya
Spain
Universitat Polite`cnica de Catalunya
Spain
University of Seville
Spain
Universidad de Sevilla (US)
Spain

View all View all

Keywords

Geometric algorithm, Computational Geometry (cs.CG), FOS: Computer and information sciences, geometric graph, :Matemàtiques i estadística::Investigació operativa::Programació matemàtica [Àrees temàtiques de la UPC], mathematical programming::90C Mathematical programming, graph augmentation, Geometry, shortcut, :Matemàtiques i estadística::Matemàtica aplicada a les ciències [Àrees temàtiques de la UPC], :90 Operations research, mathematical programming::90C Mathematical programming [Classificació AMS], :68 Computer science::68Q Theory of computing [Classificació AMS], Shortcut, :Matemàtiques i estadística::Anàlisi numèrica [Àrees temàtiques de la UPC], Classificació AMS::65 Numerical analysis::65D Numerical approximation and computational geometry, Algebraic, Diameter, Informàtica, :14 Algebraic geometry::14Q Computational aspects in algebraic geometry [Classificació AMS], Programació (Matemàtica), :65 Numerical analysis::65D Numerical approximation and computational geometry [Classificació AMS], Geometria algèbrica, Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa::Programació matemàtica, diameter, Anàlisi numèrica, Classificació AMS::90 Operations research, Programming (Mathematics), Discrete optiization, Graph augmentation, Classificació AMS::14 Algebraic geometry::14Q Computational aspects in algebraic geometry, Àrees temàtiques de la UPC::Matemàtiques i estadística::Anàlisi numèrica, Complexity, :Matemàtiques i estadística::Àlgebra [Àrees temàtiques de la UPC], Classificació AMS::90 Operations research, mathematical programming::90C Mathematical programming, Computer science, 004, Geometry, Algebraic, Àrees temàtiques de la UPC::Matemàtiques i estadística::Àlgebra, Classificació AMS::68 Computer science::68Q Theory of computing, Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica aplicada a les ciències, Discrete optimization, Computer Science - Computational Geometry, Networks, Geometric graph, Numerical analysis, ddc: ddc:004

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	2
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average