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

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

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

(21)

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

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)