2020-02-19T13:54:49Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000320152018-03-30T07:23:32Z01164:02592:02640:02641
An Optimal File Transfer on a Path Network with 2 - level Arc Cost and Positive DemandsAn Optimal File Transfer on a Path Network with 2 - level Arc Cost and Positive Demandsjpnhttp://id.nii.ac.jp/1001/00032015/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=32015&item_no=1&attribute_id=1&file_no=1Copyright (c) 2001 by the Information Processing Society of JapanFaculty of Engineering GIFU University Yoshihiro, KanekoA 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）2001115(2001-AL-081)61672001-11-272009-06-30