Fast algorithms for diameter-optimally augmenting paths

DOI10.1007/978-3-662-47672-7_55MaRDI QIDQ3448826zbMATH OpenOpenAlexFDO

Authors Ulrike Große, Joachim Gudmundsson, Christian Knauer, Fabian Stehn, Michiel Smid

Publication date 27 October 2015

Published in Automata, Languages, and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-47672-7_55

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Recommendations

• Fast algorithms for diameter-optimally augmenting paths and trees
• Almost optimal algorithms for diameter-optimally augmenting trees

Cites work

• A decomposition of multidimensional point sets with applications to k -nearest-neighbors and n -body potential fields
• Augmenting outerplanar graphs to meet diameter requirements
• Augmenting the connectivity of planar and geometric graphs
• Augmenting trees to meet biconnectivity and diameter constraints
• Bounded-diameter minimum-cost graph problems
• Computing Best and Worst Shortcuts of Graphs Embedded in Metric Spaces
• Computing the dilation of edge-augmented graphs in metric spaces
• Decreasing the diameter of bounded degree graphs
• Design networks with bounded pairwise distance
• Diameter bounds for altered graphs
• Diameter increase caused by edge deletion
• How to decrease the diameter of triangle-free graphs
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Improving the Stretch Factor of a Geometric Network by Edge Augmentation
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• The parametric complexity of graph diameter augmentation

Cited in

(17)

• Computing the dilation of edge-augmented graphs in metric spaces
• Geometric path problems with violations
• Computing optimal shortcuts for networks
• Almost optimal algorithms for diameter-optimally augmenting trees
• Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
• Shortcut sets for the locus of plane Euclidean networks
• Polynomial-Time Highest-Gain Augmenting Path Algorithms for the Generalized Circulation Problem
• A linear-time algorithm for discrete radius optimally augmenting paths in a metric space
• Almost optimal algorithms for diameter-optimally augmenting trees
• Shortcuts for the circle
• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• Fast algorithms for diameter-optimally augmenting paths and trees
• A linear-time algorithm for radius-optimally augmenting paths in a metric space
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Algorithms for radius-optimally augmenting trees in a metric space
• Shortcuts for the circle

This page was built for publication: Fast algorithms for diameter-optimally augmenting paths

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