A new linear-time algorithm for centroid decomposition

DOI10.1007/978-3-030-32686-9_20zbMATH Open1539.68217MaRDI QIDQ6536262FDOQ6536262

Authors Davide Della Giustina, Nicola Prezza, Rossano Venturini 

Publication date 19 April 2024

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• On the centroid of increasing trees
• A generalized algorithm for centrality problems on trees
• The accelerated centroid decomposition technique for optimal parallel tree evaluation in logarithmic time
• A self-stabilizing algorithm for finding weighted centroid in trees
• Algorithms for finding P-centers on a weighted tree (for relatively small P)

Cites Work

• scientific article; zbMATH DE number 1754590 (Why is no real title available?)
• A data structure for dynamic trees
• About groups of straight lines
• Binary jumbled pattern matching on trees and tree-like structures
• Compressed cache-oblivious string B-tree
• Efficient counting of square substrings in a tree
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• On the weak prefix-search problem
• Succinct ordinal trees with level-ancestor queries

This page was built for publication: A new linear-time algorithm for centroid decomposition

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