Reference no: EM13684447

Algorithm problem and need specific solution:
3. Pipes on a tree
You are given an un-rooted tree T with n vertices (notes in this tree, say, have degree at most 3). You are
also given a set with m paths Π = {π1, . . . , πm}. Here a path is defined by its two unique endpoints, since
the path in tree between any pair of vertices is unique. Provide an algorithm that computes the largest set
X ⊆ Π, such that no pair of paths in X share a vertex.
For full credit, your algorithm should be as fast as possible.