Time-Efficient Multicast to Local Vertices in Star Interconnection Networks under the Single-Port Model
Summary :
In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme for the star graph of dimension n in 1.3125log2 n + O(log log n) time units. This running time is at most 1.3125 times of that of an optimal scheme.
- Publication
- IEICE TRANSACTIONS on Information Vol.E87-D No.2 pp.315-321
- Publication Date
- 2004/02/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Foundations of Computer Science)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Satoshi FUJITA, "Time-Efficient Multicast to Local Vertices in Star Interconnection Networks under the Single-Port Model" in IEICE TRANSACTIONS on Information,
vol. E87-D, no. 2, pp. 315-321, February 2004, doi: .
Abstract: In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme for the star graph of dimension n in 1.3125log2 n + O(log log n) time units. This running time is at most 1.3125 times of that of an optimal scheme.
URL: https://global.ieice.org/en_transactions/information/10.1587/e87-d_2_315/_p
Copy
@ARTICLE{e87-d_2_315,
author={Satoshi FUJITA, },
journal={IEICE TRANSACTIONS on Information},
title={Time-Efficient Multicast to Local Vertices in Star Interconnection Networks under the Single-Port Model},
year={2004},
volume={E87-D},
number={2},
pages={315-321},
abstract={In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme for the star graph of dimension n in 1.3125log2 n + O(log log n) time units. This running time is at most 1.3125 times of that of an optimal scheme.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - Time-Efficient Multicast to Local Vertices in Star Interconnection Networks under the Single-Port Model
T2 - IEICE TRANSACTIONS on Information
SP - 315
EP - 321
AU - Satoshi FUJITA
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 2
JA - IEICE TRANSACTIONS on Information
Y1 - February 2004
AB - In this paper, we consider the problem of constructing a multicast tree in the star graph under the single-port communication model. Unlike previous studies for constructing space-efficient multicast trees, we adopt the completion time of each multicast as the objective function to be minimized. In particular, we study a special case of the problem in which all destination vertices are immediate neighbors of the source vertex, and propose a multicast scheme for the star graph of dimension n in 1.3125log2 n + O(log log n) time units. This running time is at most 1.3125 times of that of an optimal scheme.
ER -
English
