[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Algorithms for rectilinear optimal multicast tree problem

  • Conference paper
  • First Online:
Algorithms and Computation (ISAAC 1992)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 650))

Included in the following conference series:

Abstract

Given a point s called the signal source and a set D of points called the sinks, a rectilinear multicast tree is defined as a tree T=(V, E) such that s ∃ V, D \(\subseteq\) V, and the length of each path on T from the source s to a sink t equals the L 1-distance from s to t. A rectilinear multicast tree is said to be optimal if the total length of T is minimized. The optimal multicast tree (OMT) problem in general is NP-complete [1, 2, 4], while the complexity of the rectilinear version is still open. In this paper, we present algorithms to solve the rectilinear optimal multicast tree (ROMT) problem. Our algorithms require O(n3k) and O(n23n) time, where n denotes ¦D¦ and k is the number of dominating layers defined by s.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. H.-A. Choi and A.-H. Esfahanian (1989) ”The Complexity of Optimal Distance-Preserving trees,” MSU-CPS-ACS-18, Technical Report of Department of Computer Science, Michigan State University.

    Google Scholar 

  2. H.-A. Choi, A.-H. Esfahanian and B. C. Houck (1988) ”Optimal Communication Trees with Application to Hypercube Multicomputer,” Proceedings of the Sixth International conference on the Theory and Application of Graph Theory.

    Google Scholar 

  3. S. E. Dreyer and R. A. Wagner, (1972) ”The Steiner Problem in Graphs,” Networks, vol. 1, pp. 195–207.

    Google Scholar 

  4. X. Lin and L. M. Ni, (1989) ”Some Theoretical Results on Multicast Communications,” MSU-CPS-ACS-17, Technical Report of Department of Computer Science, Michigan State University.

    Google Scholar 

  5. D. E. Knuth, (1971) ”Optimal Binary Search Trees,” Acta Informatica, vol. 1, pp. 14–25.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Information Science, Academia Sinica, Taiwan, R. O. C.

    Jan-Ming Ho, M. T. Ko, Tze-Heng Ma & Ting-Yi Sung

Authors
  1. Jan-Ming Ho
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. M. T. Ko
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Tze-Heng Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ting-Yi Sung
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Toshihide Ibaraki Yasuyoshi Inagaki Kazuo Iwama Takao Nishizeki Masafumi Yamashita

Rights and permissions

Reprints and permissions

Copyright information

© 1992 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Ho, JM., Ko, M.T., Ma, TH., Sung, TY. (1992). Algorithms for rectilinear optimal multicast tree problem. In: Ibaraki, T., Inagaki, Y., Iwama, K., Nishizeki, T., Yamashita, M. (eds) Algorithms and Computation. ISAAC 1992. Lecture Notes in Computer Science, vol 650. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-56279-6_63

Download citation

  • DOI: https://doi.org/10.1007/3-540-56279-6_63

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-56279-5

  • Online ISBN: 978-3-540-47501-9

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation