Skip to main content
SpringerLink
Log in

On the complexity of an optimal routing tree problem

  • Published:
Acta Mathematicae Applicatae Sinica Aims and scope Submit manuscript

Abstract

A routing tree for a set of tasks is a decision tree which assigns the tasks to their destinations according to the features of the tasks. A weighted routing tree is one with costs attached to each link of the tree. Links of the same feature have the same cost. It is proved that the problem of finding a routing tree of the minimum cost for a given set of tasks of two features is NP-complete.

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

References

  1. D.-Z. Du, F. K. Hwang, M. T. Shing and T. Witbold, Optimal Routing Trees for theAT&T Advanced-800 Service, IEEE Transactions on Circuits, to Appear.

  2. M. R. Garey and D. S. Johnson, Computers and Intractability, Freeman, San Francisco, 1979.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Applied Mathematics, Academia Sinica, China

    Du Dingzhu

  2. State University of New York at Stony Brook, USA

    Ker-I Ko

Authors
  1. Du Dingzhu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ker-I Ko
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was supported in part by theNSF grantsDCR-8501226 andDCR-8696135. Part of this work was done while the first author was at the Mathematical Sciences Research Institute, Berkeley, California, and while the second author was at the Department of Mathematics, University of California, Santa Barbara, California.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Du, D., Ker-I, K. On the complexity of an optimal routing tree problem. Acta Mathematicae Applicatae Sinica 5, 68–80 (1989). https://doi.org/10.1007/BF02006188

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation