Shortcut sets for the locus of plane Euclidean networks

DOI10.1016/J.AMC.2018.04.010MaRDI QIDQ2335528zbMATH OpenOpenAlexWikidataFDO

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)

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

zbMATH Keywords

augmentation problemdiametereuclidean networknetwork designshortcut set

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(11)

• Computing optimal shortcuts for networks
• Minimizing the diameter of a network using shortcut edges
• Euclidean chains and their shortcuts
• Shortcutting directed and undirected networks with a degree constraint
• Computing optimal shortcuts for networks
• Shortcut sets for plane Euclidean networks (extended abstract)
• Shortcuts for the circle
• Euclidean chains and their shortcuts
• Finding the best shortcut in a geometric network
• Shortcuts for the circle
• Algorithms for distance problems in continuous graphs

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)