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.
A Synthesis of an Optimal File Transfer on a File Transmission Net
Yoshihiro KANEKO Shoji SHINODA Kazuo HORIUCHI
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 1993/03/25
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on the 5th Karuizawa Workshop on Circuits and Systems)
minimum spanning tree, shortest path, vertex cost, arc cost, vertex demand,
Full Text: PDF>>
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.