Minimizing diameters of dynamic trees

DOI10.1007/3-540-63165-8_184MaRDI QIDQ4571959zbMATH OpenOpenAlexFDO

Authors Stephen Alstrup, Jacob Holm, Kristian de Lichtenberg, Mikkel Thorup

Publication date 4 July 2018

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

Full work available at URL https://doi.org/10.1007/3-540-63165-8_184

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Minimum Diameter Spanning Trees and Related Problems
• On the treewidth of dynamic graphs
• On the treewidth of dynamic graphs
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• Approximating minimum k-section in trees with linear diameter
• Path minima queries in dynamic weighted trees
• scientific article; zbMATH DE number 1420900
• scientific article; zbMATH DE number 751126
• Maintaining minimum spanning trees in dynamic graphs
• On the minimum diameter spanning tree problem

Cites work

• A simple parallel algorithm for computing the diameters of all vertices in a tree and its application
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Maintaining spanning trees of small diameter

Cited in

(14)

• Almost optimal dynamic 2-3 trees
• Dynamic Euclidean minimum spanning trees and extrema of binary functions
• Succinct data structures for nearest colored node in a tree
• String indexing for top-\(k\) close consecutive occurrences
• Tree compression with top trees
• Minimizing the continuous diameter when augmenting a tree with a shortcut
• Gapped indexing for consecutive occurrences
• Longest common extensions in trees
• An Optimal Rebuilding Strategy for a Decremental Tree Problem
• Tight bounds for top tree compression
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay
• String indexing for top-\(k\) close consecutive occurrences
• RDDGN: minimizing the total resistance distance and diameter using graph neural networks

This page was built for publication: Minimizing diameters of dynamic trees

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