Minimizing Average Shortest Path Distances via Shortcut Edge Addition

DOI10.1007/978-3-642-03685-9_21MaRDI QIDQ3638883zbMATH OpenOpenAlexFDO

Authors Adam Meyerson, Brian Tagiku

Publication date 28 October 2009

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03685-9_21

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Paths and cycles (05C38)

Recommendations

• Minimizing the diameter of a network using shortcut edges
• The Shortcut Problem – Complexity and Approximation
• The shortcut problem - complexity and algorithms
• Finding the best shortcut in a geometric network
• Shortcutting directed and undirected networks with a degree constraint

Cited in

(20)

• Demand-aware network designs of bounded degree
• Minimizing the diameter of a network using shortcut edges
• Some results about the inset edge and average distance of trees
• Strengthening ties towards a highly-connected world
• The shortcut problem - complexity and algorithms
• Optimization of the critical diameter and average path length of social networks
• Augmenting weighted graphs to establish directed point-to-point connectivity
• On the maximum betweenness improvement problem
• Improving the betweenness centrality of a node by adding links
• Using shortcut edges to maximize the number of triangles in graphs
• Improved approximation for prize-collecting red-blue median
• Local search algorithms for the red-blue median problem
• Mechanism design for building optimal bridges between regions
• Converting a network into a small-world network: fast algorithms for minimizing average path length through link addition
• Network structure optimization for social networks by minimizing the average path length
• Location of speed-up subnetworks
• On the fixed-parameter tractability of the maximum connectivity improvement problem
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Impact of the topology of urban streets on mobility optimization
• Shortcutting directed and undirected networks with a degree constraint

This page was built for publication: Minimizing Average Shortest Path Distances via Shortcut Edge Addition

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