Skip to main content
SpringerLink
Log in

Optimal Edge Ranking of Trees in Linear Time

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract.

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Hong Kong, Pokfulam Road, Hong Kong. twlam@cs.hku.hk. This research was supported in part by the University of Hong Kong CRCG Grant 337/065/0026., HK

    T. W. Lam

  2. Management Information Office, City University of Hong Kong, Kowloon, Hong Kong. yolanda.yue@cityu.edu.hk., HK

    F. L. Yue

Authors
  1. T. W. Lam
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. F. L. Yue
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Received April 22, 1998; revised November 19, 1998.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Lam, T., Yue, F. Optimal Edge Ranking of Trees in Linear Time. Algorithmica 30, 12–33 (2001). https://doi.org/10.1007/s004530010076

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/s004530010076

Search

Navigation