Let $T=(V,E)$ be tree and each edge has a positive scalar weight. I need to print all paths in the tree and then sort the weight of edges in each paths. it needs $O(n^3\log(n))$ time. To solve this problem we can rooted the tree in a leaf and print all vertices by preorder algorithm and in each step we insert the new edge weight. After meeting all vertices we can delete the root and consider another leaf as the root. The complexity seems $O(n^2\log(n)).$ Can we reduce the complexity, for example, $O(n^2)$?
3
-
$\begingroup$ Should all paths be printed as a sorted sequence of edges (not necessarily in the order they appear in each path), or do you mean something else? $\endgroup$– András SalamonCommented Mar 14, 2018 at 10:11
-
$\begingroup$ I exactly want to do that! Printing sorted sequence of edges according to their weights in each path. $\endgroup$– A.R.SCommented Mar 14, 2018 at 10:31
-
$\begingroup$ Cross-posted: cs.stackexchange.com/q/89311/755, cstheory.stackexchange.com/q/40222/5038. Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. Please pick one site where you want this to appear. You already received advice there that before reposting on CS.SE, "think of adding more details on what you have tried so far and what did not work; people will be more willing to help if you show that you have already thought about the problem." $\endgroup$– D.W. ♦Commented Mar 14, 2018 at 16:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can't do better than $\Omega(n^3)$ running time.
In a tree, there is a path between every pair of vertices, so there are $\Theta(n^2)$ paths. The average path length can be $\Theta(n)$. So the total length of the output can be $\Theta(n^3)$. Obviously, no algorithm can run faster than that, since it takes at least $\Theta(n^3)$ time just to write out the output.
