|
|
For Full-Text PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
|
An Optimal File Transfer on Networks with Plural Original Files
Yoshihiro KANEKO Shoji SHINODA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E85-A
No.12
pp.2913-2922
Publication Date: 2002/12/01
Online ISSN:
DOI:
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword:
file transfer, original files, single source, minimum spanning tree with degree constraints,
Full Text: PDF>>
Summary:
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.
|
|
