Finding diameter-reducing shortcuts in trees

DOI10.1007/978-3-031-38906-1_12arXiv2305.17385OpenAlexW4385317361MaRDI QIDQ6179408

Stefano Leucci, Luciano Gualà, Davide Bilò, Luca Pepè Sciarria

Publication date: 16 January 2024

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

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

zbMATH Keywords

approximation algorithmstime-efficient algorithmsfast diameter computationtree diameter augmentation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Data structures (68P05)

Cites Work

• Unnamed Item
• Augmenting graphs to minimize the diameter
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Algorithms for radius-optimally augmenting trees in a metric space
• Clustering to minimize the maximum intercluster distance
• On the minimum-cardinality-bounded-diameter and the bounded-cardinality- minimum-diameter edge addition problems
• Augmenting trees to meet biconnectivity and diameter constraints
• Almost optimal algorithms for diameter-optimally augmenting trees
• Minimizing the continuous diameter when augmenting a geometric tree with a shortcut
• The parametric complexity of graph diameter augmentation
• Fast Algorithms for Finding Nearest Common Ancestors
• Minimizing the Diameter of a Network Using Shortcut Edges
• Diameter increase caused by edge deletion
• A Near-Optimal Algorithm for Finding an Optimal Shortcut of a Tree
• Fast Algorithms for Diameter-Optimally Augmenting Paths and Trees
• An improved algorithm for diameter-optimally augmenting paths in a metric space
• A linear-time algorithm for radius-optimally augmenting paths in a metric space
• Algorithms for diameters of unicycle graphs and diameter-optimally augmenting trees

This page was built for publication: Finding diameter-reducing shortcuts in trees