http://swrc.ontoware.org/ontology#TechnicalReport
An Optimal File Transfer on a Path Network with 2 - level Arc Cost and Positive Demands
ja
Faculty of Engineering GIFU University
Yoshihiro Kaneko
A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to distribute with the minimum total cost copies of a certain file of information from source vertex to others on N by the respective vertices' copy demand numbers. The problem is NP-hard for a general file transmission net. Some class of N on which polynomial time algorithm to solve the problem has been known. So far we assumed that N has a linear function as an arc cost. In this report we suppose that N has a directed path graph structure with its arc costs being 2-level step functions. As a result we show that the problem can be solved in O(n2) where n is the number of vertices.
A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to distribute, with the minimum total cost, copies of a certain file of information from source vertex to others on N by the respective vertices' copy demand numbers. The problem is NP-hard for a general file transmission net. Some class of N on which polynomial time algorithm to solve the problem has been known. So far, we assumed that N has a linear function as an arc cost. In this report, we suppose that N has a directed path graph structure with its arc costs being 2-level step functions. As a result, we show that the problem can be solved in O(n2), where n is the number of vertices.
AN1009593X
情報処理学会研究報告アルゴリズム（AL）
2001
115(2001-AL-081)
61-67
2001-11-27