A Synthesis of an Optimal File Transfer on a File Transmission Net

Yoshihiro KANEKO  Shoji SHINODA  Kazuo HORIUCHI  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A   No.3   pp.377-386
Publication Date: 1993/03/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on the 5th Karuizawa Workshop on Circuits and Systems)
Category: 
Keyword: 
minimum spanning tree,  shortest path,  vertex cost,  arc cost,  vertex demand,  

Full Text: PDF>>
Buy this Article



Summary: 
A file transmission net N is a directed communication net with vertex set V and arc set B such that each arc e has positive cost ca(e) and each vertex u in V has two parameters of positive cost cv(u) and nonnegative integral demand d(u). Some information to be distributed through N is supposed to have been written in a file and the written file is denoted by J, where the file means an abstract concept of information carrier. In this paper, we define concepts of file transfer, positive demand vertex set U and mother vertex set M, and we consider a problem of distributing d(v) copies of J through a file transfer on N from a vertex v1 to every vertex v in V. As a result, for N such that MU, we propose an O(nm+n2 log n) algorithm, where n=|V| and m=|B|, for synthesizing a file transfer whose total cost of transmitting and making copies of J is minimum on N.