Timeline for Separate all leaves of a weighted tree with minimum weight cuts
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17, 2012 at 10:27 | vote | accept | Paresh | ||
| Oct 30, 2012 at 22:31 | comment | added | Paresh | @Joe From your comments to the question, I had deduced this, and tried to implement it using a single DFS. It did not work out. I must have made a mistake in implementing it, or in the reduction of my original problem to this problem. I will explore both and update. | |
| Oct 30, 2012 at 22:27 | comment | added | Paresh | @Raphael 1) Yes, that is what he means. 2) Paragraph 1 was the base case, paragraph 2 is the generalization. Any node of height more than 1 might have leaves as its descendants, and the path to each leaf will consist of more than one edge. For each such path, we consider the smallest edge in it. This is the edge that needs to be removed to cut off this path with minimum cost. And among these $d-1$ paths, we cut-off the $d-2$ paths with the min edge costs. 3) Any internal (non-leaf) node can be considered to be the root. If no such node exists, the tree is just two nodes with one edge - trivial | |
| Oct 30, 2012 at 21:44 | comment | added | Raphael | 1) "If v has degree d and d−1 children, then the d−2 smallest edges are added to the cut." -- here you mean $d-1$ leaves and $d-2$ of the edges connecting those, I guess? 2) Paragraph one is redundant? ( 3) For the presentation, note that the tree was not assumed to be rooted.) I don't quite follow your idea, in particular why you find the minimum number. But that might be my tiredness. | |
| Oct 30, 2012 at 20:22 | history | answered | Joe | CC BY-SA 3.0 |