Centroid Decomposition of tree

[abhayptp]

Centroid decomposition is a divide and conquer approach which helps in making distance queries on large trees in an efficient way.

For example, using centroid decomposition on tree(n vertices), we can find the number of nodes at distance of x from vertex v in O(log² n) time and O(n log (n)) memory. Due to low memory requirements, it can be used on large graphs.

References:

https://courses.csail.mit.edu/6.897/spring05/lec.html

https://www.degruyter.com/view/j/crll.1869.issue-70/crll.1869.70.185/crll.1869.70.185.xml

https://eudml.org/doc/148084

CC: @dcoudert

Component: graph theory

Issue created by migration from https://trac.sagemath.org/ticket/27555

[abhayptp]

comment:1

I can implement this algorithm in sage. I have coded it multiple times. Suggestions are invited on the implementation part.

[embray]

comment:3

As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).