A centroid labelling technique and its application to path selection in trees

DOI10.1007/3-540-63307-3_75zbMath1497.68393OpenAlexW74823494MaRDI QIDQ5096953

Sarnath Ramnath, Hong Shen

Publication date: 19 August 2022

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

Full work available at URL: https://doi.org/10.1007/3-540-63307-3_75

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Data structures (68P05)

Cites Work

• Optimal parallel selection in sorted matrices
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• Efficient parallel algorithms for r-dominating set and p-center problems on trees
• Parallel Merge Sort
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• An Algorithmic Approach to Network Location Problems. II: Thep-Medians
• An $O(n\log ^2 n)$ Algorithm for the kth Longest Path in a Tree with Applications to Location Problems
• Finding kth paths and p-centers by generating and searching good data structures