| Article ID: | iaor20121025 |
| Volume: | 30 |
| Issue: | 1 |
| Start Page Number: | 12 |
| End Page Number: | 33 |
| Publication Date: | May 2001 |
| Journal: | Algorithmica |
| Authors: | Lam T W, Yue F L |
| Keywords: | polynomial programs, edge analysis, trees |
Given a tree, finding an optimal node ranking and finding an optimal edge ranking are interesting computational problems. The former problem already has a linear time algorithm in the literature. For the latter, only recently polynomial time algorithms have been revealed, and the best known algorithm requires more than quadratic time. In this paper we present a new approach for finding an optimal edge ranking of a tree, improving the time complexity to linear.