Centroid decomposition(or also known as separator decomposition) is a divide and conquer decomposition of tree which helps in making distance queries on trees efficiently. For example, using centroid decomposition, we can query count of vertices at distance x from vertex v in O(log^2 n) time and O(n log(n)) memory. Due to low memory usage, it can be used on large trees. Currently, I am not able to find any paper explaining the approach. But this technique is quite famous among competitive programming community. And I think that it also has applications in real world. If anyone wants, I can link some blogs, lecture notes related to this technique or write it up myself :) I wish to contribute on this if it is agreed upon and there is not any thing implemented of this sort till now.
-- You received this message because you are subscribed to the Google Groups "sage-devel" group. To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+unsubscr...@googlegroups.com. To post to this group, send email to sage-devel@googlegroups.com. Visit this group at https://groups.google.com/group/sage-devel. For more options, visit https://groups.google.com/d/optout.
