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

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)

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

• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• 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
• 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

(10)

• Euclidean chains and their shortcuts
• Minimizing the diameter of a network using shortcut edges
• Computing optimal shortcuts for networks
• scientific article; zbMATH DE number 7561369 (Why is no real title available?)
• 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)