Minimizing the diameter of a network using shortcut edges

DOI10.1007/978-3-642-13731-0_39MaRDI QIDQ3569910zbMATH OpenOpenAlexFDO

Authors Erik D. Demaine, Morteza Zadimoghaddam

Publication date 22 June 2010

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1721.1/62215

zbMATH Keywords

approximation algorithmsnetwork designnetwork repair

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25)

Recommendations

• Shortcutting directed and undirected networks with a degree constraint
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Shortcut sets for the locus of plane Euclidean networks
• scientific article; zbMATH DE number 6792403
• Shortcut sets for plane Euclidean networks (extended abstract)

Cited in

(28)

• Algorithms for radius-optimally augmenting trees in a metric space
• Strengthening ties towards a highly-connected world
• Algorithms for radius-optimally augmenting trees in a metric space
• Link-Length Minimization in Networks
• RDDGN: minimizing the total resistance distance and diameter using graph neural networks
• Optimization of the critical diameter and average path length of social networks
• Vertex downgrading to minimize connectivity
• Shortcut sets for the locus of plane Euclidean networks
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Augmenting weighted graphs to establish directed point-to-point connectivity
• Almost optimal algorithms for diameter-optimally augmenting trees
• On the maximum betweenness improvement problem
• Finding diameter-reducing shortcuts in trees
• Polarization reduction by minimum‐cardinality edge additions: Complexity and integer programming approaches
• Improving the betweenness centrality of a node by adding links
• Using shortcut edges to maximize the number of triangles in graphs
• Minimizing Average Shortest Path Distances via Shortcut Edge Addition
• Bicriteria approximation for minimum dilation graph augmentation
• Mechanism design for building optimal bridges between regions
• Location of speed-up subnetworks
• On the fixed-parameter tractability of the maximum connectivity improvement problem
• Almost optimal algorithms for diameter-optimally augmenting trees
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Impact of the topology of urban streets on mobility optimization
• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• Shortcutting directed and undirected networks with a degree constraint
• Augmenting graphs to minimize the radius
• Finding diameter-reducing shortcuts in trees

This page was built for publication: Minimizing the diameter of a network using shortcut edges

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