An Optimal File Transfer on a Path Network with 2-level Arc Cost and Positive Demands
スポンサーリンク
概要
- 論文の詳細を見る
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(n^2), where n is the number of vertices.
- 一般社団法人情報処理学会の論文
- 2001-11-27
著者
関連論文
- Estimation of Cell Biomass in Plant Cell Suspensions by the Osmotic Pressure Measurement of Culture Broth
- Efficient Production of Chitinase by Immobilized Wasabia japonica Cells in Double-Layered Gel Fibers
- An Optimal File Transfer on a Path Network with 2-level Arc Cost and Positive Demands
- A Synthesis of a Forest-Type Optimal File Transfer on a File Transmission Net with Source Vertices
- On an Optimal File Transfer on an Arborescence-Net with Constraints on Copying Numbers
- On an Optimum File Transfer on a File Transmission Net (Special Section of Letters Selected from the 1993 IEICE Spring Conference)
- A Synthesis of an Optimal File Transfer on a File Transmission Net (Special Section on the 5th Karuizawa Workshop on Circuits and Systems)
- An Optimal File Transfer on Networks with Plural Original Files(Regular Sction)
- The Complexity of an Optimal File Transfer Problem
- On a Problem of Designing a 2-Switch Node Network
- B-20-9 The utilization of betwenness for DSDV
- The rank difference of node centrality between global and local graphs
- The rank difference of node centrality between global and local graphs
- The rank difference of node centrality between global and local graphs
- The rank difference of node centrality between global and local graphs