Almost optimal algorithms for diameter-optimally augmenting trees

DOI10.1016/J.TCS.2022.07.028MaRDI QIDQ2167895zbMATH OpenOpenAlexFDO

Authors D. Bilò

Publication date 1 September 2022

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1809.08822

zbMATH Keywords

augmentation problemgraph diametertime-efficient algorithmstrees

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Almost optimal algorithms for diameter-optimally augmenting trees
• Finding diameter-reducing shortcuts in trees
• Fast algorithms for diameter-optimally augmenting paths and trees
• Fast algorithms for diameter-optimally augmenting paths

Cites work

• A linear-time algorithm for radius-optimally augmenting paths in a metric space
• A near-optimal algorithm for finding an optimal shortcut of a tree
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Algorithms for radius-optimally augmenting trees in a metric space
• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• Augmenting outerplanar graphs to meet diameter requirements
• Augmenting trees to meet biconnectivity and diameter constraints
• Decreasing the diameter of bounded degree graphs
• Diameter bounds for altered graphs
• Diameter increase caused by edge deletion
• Fast algorithms for diameter-optimally augmenting paths and trees
• Finding the upper envelope of n line segments in O(n log n) time
• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
• Minimizing the diameter of a network using shortcut edges
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• The parametric complexity of graph diameter augmentation

Cited in

(9)

• On improving matchings in trees, via bounded-length augmentations
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• scientific article; zbMATH DE number 7205039 (Why is no real title available?)
• Algorithms and Data Structures
• Mixed covering of trees and the augmentation problem with odd diameter constraints
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees
• Finding diameter-reducing shortcuts in trees
• Finding diameter-reducing shortcuts in trees
• Bicriteria approximation for minimum dilation graph augmentation

This page was built for publication: Almost optimal algorithms for diameter-optimally augmenting trees

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