repeating's blog

Centeroid decomposition
By repeating, history, 7 years ago, In English

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

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
7 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

The most famous application of this technique is for the following types of problems:

  • Compute number of paths in a tree T satisfying some property P
  • Compute the path in a tree T which has highest/lowest some property P

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.

→ Reply