Shortcut sets for the locus of plane Euclidean networks

DOI10.1016/J.AMC.2018.04.010zbMATH Open1427.05215arXiv1604.03878OpenAlexW2962910869WikidataQ129918665 ScholiaQ129918665MaRDI QIDQ2335528FDOQ2335528

Authors: Delia Garijo, Antonio González, M. L. Puertas, Paula R. Ribeiro, Jose Cáceres, A. Márquez 

Publication date: 14 November 2019

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: We study the problem of augmenting the locus $mathcal{N}_{ell}$ of a plane Euclidean network $mathcalN$ by inserting iteratively a finite set of segments, called emph{shortcut set}, while reducing the diameter of the locus of the resulting network. There are two main differences with the classical augmentation problems: the endpoints of the segments are allowed to be points of $mathcal{N}_{ell}$ as well as points of the previously inserted segments (instead of only vertices of $mathcalN$), and the notion of diameter is adapted to the fact that we deal with $mathcal{N}_{ell}$ instead of $mathcalN$. This increases enormously the hardness of the problem but also its possible practical applications to network design. Among other results, we characterize the existence of shortcut sets, compute them in polynomial time, and analyze the role of the convex hull of $mathcal{N}_{ell}$ when inserting a shortcut set. Our main results prove that, while the problem of minimizing the size of a shortcut set is NP-hard, one can always determine in polynomial time whether inserting only one segment suffices to reduce the diameter.

Full work available at URL: https://arxiv.org/abs/1604.03878

Recommendations

• Shortcut sets for plane Euclidean networks (extended abstract)
• Computing optimal shortcuts for networks
• scientific article; zbMATH DE number 6792403
• Finding the best shortcut in a geometric network
• Minimizing the diameter of a network using shortcut edges

zbMATH Keywords

diameternetwork designaugmentation problemshortcut seteuclidean network

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• Visibility and intersection problems in plane geometry
• Computing the dilation of edge-augmented graphs in metric spaces
• Euclidean chains and their shortcuts
• On the complexity of locating linear facilities in the plane
• Network farthest-point diagrams
• Linear time algorithm for optimal feed-link placement
• Arrangements of curves in the plane --- topology, combinatorics, and algorithms
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• The generalized diameter of a graph
• Title not available (Why is that?)
• The continuous center set of a network
• Fast algorithms for diameter-optimally augmenting paths
• Plane geometric graph augmentation: a generic perspective
• How to decrease the diameter of triangle-free graphs
• Sparse geometric graphs with small dilation
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
• Spanners and message distribution in networks.
• Identification of influential spreaders based on classified neighbors in real-world complex networks
• Shortcuts for the circle

Cited In (10)

• Euclidean chains and their shortcuts
• Minimizing the diameter of a network using shortcut edges
• Title not available (Why is that?)
• Computing optimal shortcuts for networks
• Finding the best shortcut in a geometric network
• Euclidean chains and their shortcuts
• Shortcutting directed and undirected networks with a degree constraint
• Shortcut sets for plane Euclidean networks (extended abstract)
• Shortcuts for the circle
• Shortcuts for the circle

This page was built for publication: Shortcut sets for the locus of plane Euclidean networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2335528)