The search functionality is under construction.
The search functionality is under construction.

An Optimal File Transfer on Networks with Plural Original Files

Yoshihiro KANEKO, Shoji SHINODA

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.12 pp.2913-2922
Publication Date
2002/12/01
Publicized
Online ISSN
DOI
Type of Manuscript
PAPER
Category
Graphs and Networks

Authors

Keyword