Abstract
In this paper, the notion of quasi-full Steiner tree (QFST) is introduced which is an extension of full Steiner tree (FST). We discuss some properties of QFST,and present a generating algorithm for obtaining a QFST or denying its existence. With this algorithm we can obtain a minimum QFST that is just the Steiner minimal tree (SMT) if it has the quasi-full topology.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
F. R. K. Chung and R. L. Graham, Steiner trees for Ladders. Ann. Discrete Math. 2(1978), 173–200.
D.Z. Du,F. K. Hwang, G. D. Song and G. Y. Ting, Steiner minimal trees on sets of four points, Discrete Comput. Ceom. 2(1987), 401–414.
D. Z. Du,F. K. Hwang and J. F. Weng, Steiner minimal trees on Zig-Zag lines,Trans. Amer. Math. soc. 278(1983), 149–156.
D. Z. Du and F. K. Hwang, Steiner minimal trees for Bar waves. Acta Math. Appl. Sinica 3(1987), 246–256.
E. N. Gilbert and H. O. Pollak, Steiner minimal trees,SIAM J. Appl. Math. 16(1968),1–29.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ding, J. (1994). Generating algorithm for quasi-full Steiner tree. In: Du, DZ., Zhang, XS. (eds) Algorithms and Computation. ISAAC 1994. Lecture Notes in Computer Science, vol 834. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58325-4_208
Download citation
DOI: https://doi.org/10.1007/3-540-58325-4_208
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58325-7
Online ISBN: 978-3-540-48653-4
eBook Packages: Springer Book Archive