Hello everybody
Recently I learned a new algorithm which is Centeroid decomposition , but I didn't find enough Information about it.
I didn't understand the usefulness of the algorithm , or when we use it !!
So would you please help and give me more information about it :D
The most famous application of this technique is for the following types of problems:
Essentially, you're fixing a vertex v and looking at all paths going through v and then removing it from the tree and recursing on the forest formed. It just happens that the centroid is the best choice of v.
An extended idea of the technique can be used to solve some query based problems, all of which exploit the fact that the "centroid tree" formed after the decomposition has height . For example, you can answer queries of the form .
Check out this blog to learn more.