patternMinor
Find node that splits tree in half
Viewed 0 times
splitsnodethatfindhalftree
Problem
Given a tree $T = (V , F)$, find an algorithm which finds $u \in V$, so in the graph $T = (V \setminus \{u\} , F)$ the size of each connected component is $\lceil |V| / 2 \rceil$ at most. What is the complexity?
Can I please have a hint?
Can I please have a hint?
Solution
Use dynamic programming to find division number of each node, For leaf nodes set it to $0$
Then recursively for parent of each leaf node set it to sum of division of it's child, and for each child because that child is not counted in division number of itself we should add its division number by one to calculate the parent division number:
$$\text{division}(v) = \Sigma (\text{division}(\text{child}_i)+1)$$
Use above recursion structure to set division number of each node, but if in some point if you have division number bigger than equal to $|V|/2$ output this node.
This is bottom up $O(|V|)$ algorithm because you will check every node at most once, and the operation which calculates division numbers is at most $\Sigma \text{ deg}(v_i) = 2|E| = 2|V-1|$.
Then recursively for parent of each leaf node set it to sum of division of it's child, and for each child because that child is not counted in division number of itself we should add its division number by one to calculate the parent division number:
$$\text{division}(v) = \Sigma (\text{division}(\text{child}_i)+1)$$
Use above recursion structure to set division number of each node, but if in some point if you have division number bigger than equal to $|V|/2$ output this node.
This is bottom up $O(|V|)$ algorithm because you will check every node at most once, and the operation which calculates division numbers is at most $\Sigma \text{ deg}(v_i) = 2|E| = 2|V-1|$.
Context
StackExchange Computer Science Q#10262, answer score: 4
Revisions (0)
No revisions yet.