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>>
Buy this Article



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.