An Optimal File Transfer on Networks with Plural Original Files
-
- KANEKO Yoshihiro
- Faculty of Engineering, Gifu University
-
- SHINODA Shoji
- Faculty of Science and Engineering, Chuo University
この論文をさがす
説明
A problem of obtaining an optimal file transfer of a file transmission net N is to consider how to transmit, with the minimum total cost, copies of a certain file of information from some vertices, called sources, to other vertices of N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net N. Some classes of N, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed, are known. In the characterization, we assumed that file given originally to the source remains at the source without being transmitted. In this paper, we relax the assumption to the one that a sufficient number of copies of the file are given to the source and those copies can be transmitted from the source to other vertices on N. Under this new assumption, we characterize a class of file transmission nets, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed. A minimum spanning tree with degree constraints plays a key role in the algorithm.
収録刊行物
-
- IEICE transactions on fundamentals of electronics, communications and computer sciences
-
IEICE transactions on fundamentals of electronics, communications and computer sciences 85 (12), 2913-2922, 2002-12-01
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1570854177488229888
-
- NII論文ID
- 110003212467
-
- NII書誌ID
- AA10826239
-
- ISSN
- 09168508
-
- 本文言語コード
- en
-
- データソース種別
-
- CiNii Articles
