Graph theory - Divide-And-Conquer Algorithm for Trees

De openkb
Aller à : Navigation, rechercher

Sommaire

Questions

I am trying to write a divide & conquer algorithm for trees. For the divide step I need an algorithm that partitions a given undirected Graph G=(V,E) with n nodes and m edges into sub-trees by removing a node . All subgraphs should have the property that they don t contain more than n/2 nodes (the tree should be split as equal as possible). First I tried to recursively remove all leaves from the tree to find the last remaining node, then I tried to find the longest path in G and remove the middle node of it. The given graph below shows that both approaches don t work:

<img src="https://i.stack.imgur.com/qNbko.png" alt="Graph">

Is there some working algorithm that does what I want (returns the node H in the above case).

Answers

I think you could do it with an algorithm like this:

Start in the root (if the tree isn t rooted, pick any node).
In each step, try to descend into the child node that has the largest subtree (the number of nodes “below” it is the biggest).
If doing that would make the number of nodes “above” bigger than n/2, stop, otherwise continue with that child.

This algorithm should be O(log n) if the tree is reasonably balanced and we have sizes of subtrees precomputed for each node. If one of those conditions doesn t apply, it would be O(n).

Source

License : cc by-sa 3.0

http://stackoverflow.com/questions/8193574/divide-and-conquer-algorithm-for-trees

Related

Outils personnels
Espaces de noms

Variantes
Actions
Navigation
Outils