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

(29)

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

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)