Finding diameter-reducing shortcuts in trees

DOI10.1016/J.JCSS.2025.103658MaRDI QIDQ6987113zbMATH OpenFDO

Authors D. Bilò, Luciano Gualà, Stefano Leucci, Luca Pepè Sciarria

Publication date 7 May 2025

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.JCSS.2025.103658

zbMATH Keywords

approximation algorithmsfast diameter computationtime-efficient algorithmstree diameter augmentation

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10) Metric embeddings as related to computational problems and algorithms (68R12) Approximation algorithms (68W25)

Cites work

• A data structure for dynamic trees
• 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
• Almost optimal algorithms for diameter-optimally augmenting trees
• An improved algorithm for diameter-optimally augmenting paths in a metric space
• Augmenting graphs to minimize the diameter
• Augmenting trees to meet biconnectivity and diameter constraints
• Clustering to minimize the maximum intercluster distance
• Diameter increase caused by edge deletion
• Fast algorithms for diameter-optimally augmenting paths and trees
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding level-ancestors in trees
• scientific article; zbMATH DE number 6792403 (Why is no real title available?)
• scientific article; zbMATH DE number 7788618 (Why is no real title available?)
• Improved approximability and non-approximability results for graph diameter decreasing problems
• Maintaining information in fully dynamic trees with top trees
• 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 level ancestor problem simplified
• The parametric complexity of graph diameter augmentation

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

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