Minimizing Average Shortest Path Distances via Shortcut Edge Addition

DOI10.1007/978-3-642-03685-9_21zbMATH Open1255.68307OpenAlexW1819194591MaRDI QIDQ3638883FDOQ3638883

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

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

Mathematics Subject Classification ID

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

Cited In (20)

• 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
• Improving the betweenness centrality of a node by adding links
• On the maximum betweenness improvement problem
• Using shortcut edges to maximize the number of triangles in graphs
• Improved approximation for prize-collecting red-blue median
• Mechanism design for building optimal bridges between regions
• Local search algorithms for the red-blue median problem
• Network structure optimization for social networks by minimizing the average path length
• Converting a network into a small-world network: fast algorithms for minimizing average path length through link addition
• Location of speed-up subnetworks
• On the fixed-parameter tractability of the maximum connectivity improvement problem
• Impact of the topology of urban streets on mobility optimization
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Shortcutting directed and undirected networks with a degree constraint
• Demand-aware network designs of bounded degree

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)