A Linear-Time Algorithm for Designing an Optimal File Transfer through an Arborescence-Net

Yoshihiro KANEKO  Reiko TASHIRO  Shoji SHINODA  Kazuo HORIUCHI 

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences  Vol.E75-A  No.7  pp.901-904
Publication Date: 1992/07/20
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section LETTER (Special Section on the 1992 IEICE Spring Conference)
Category: 
Keyword: 
graph,  arborescence,  vertex demand,  vertex cost,  arc cost, 

Full Text: PDF(260.6KB)

Summary: 
An arborescence-net N is a directed connected communication network with arborescence structure. 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 letter, we consider a problem of distributing copies of J through N from the root vertex to every vertex, where the cost of transmitting a copy of J through each arc, the cost of making a copy of J at each vertex and the number of copies of J needed at each vertex in N are defined. Definig a file transfer on N, we give a method for designing an optimal file transfer by which we mean a file transfer whose total cost of transmitting and making copies of J is minimum on N.