The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
파일 전송망의 최적 파일 전송을 구하는 문제 N 최소한의 총 비용으로 특정 정보 파일의 복사본을 소스라고 불리는 일부 정점에서 다른 정점으로 전송하는 방법을 고려하는 것입니다. N 각 정점의 복사 요구 수에 따라. 이 문제는 NP-하드 일반 파일 전송망의 경우 N. 일부 클래스 N최적의 파일 전송을 얻기 위한 다항식 시간 알고리즘이 각각 설계될 수 있는 가 알려져 있습니다. 특성화에서는 원래 소스에 제공된 파일이 전송되지 않고 소스에 남아 있다고 가정했습니다. 본 논문에서는 충분한 수의 파일 복사본이 소스에 제공되고 해당 복사본이 소스에서 다른 정점으로 전송될 수 있다는 가정을 완화합니다. N. 이 새로운 가정 하에서 우리는 최적의 파일 전송을 얻기 위한 다항식 시간 알고리즘을 설계할 수 있는 파일 전송 네트워크 클래스를 특성화합니다. 차수 제약이 있는 최소 스패닝 트리는 알고리즘에서 중요한 역할을 합니다.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
부
Yoshihiro KANEKO, Shoji SHINODA, "An Optimal File Transfer on Networks with Plural Original Files" in IEICE TRANSACTIONS on Fundamentals,
vol. E85-A, no. 12, pp. 2913-2922, December 2002, doi: .
Abstract: A problem of obtaining an optimal file transfer of a file transmission net N is to consider how to transmit, with the minimum total cost, copies of a certain file of information from some vertices, called sources, to other vertices of N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net N. Some classes of N, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed, are known. In the characterization, we assumed that file given originally to the source remains at the source without being transmitted. In this paper, we relax the assumption to the one that a sufficient number of copies of the file are given to the source and those copies can be transmitted from the source to other vertices on N. Under this new assumption, we characterize a class of file transmission nets, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed. A minimum spanning tree with degree constraints plays a key role in the algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e85-a_12_2913/_p
부
@ARTICLE{e85-a_12_2913,
author={Yoshihiro KANEKO, Shoji SHINODA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An Optimal File Transfer on Networks with Plural Original Files},
year={2002},
volume={E85-A},
number={12},
pages={2913-2922},
abstract={A problem of obtaining an optimal file transfer of a file transmission net N is to consider how to transmit, with the minimum total cost, copies of a certain file of information from some vertices, called sources, to other vertices of N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net N. Some classes of N, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed, are known. In the characterization, we assumed that file given originally to the source remains at the source without being transmitted. In this paper, we relax the assumption to the one that a sufficient number of copies of the file are given to the source and those copies can be transmitted from the source to other vertices on N. Under this new assumption, we characterize a class of file transmission nets, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed. A minimum spanning tree with degree constraints plays a key role in the algorithm.},
keywords={},
doi={},
ISSN={},
month={December},}
부
TY - JOUR
TI - An Optimal File Transfer on Networks with Plural Original Files
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2913
EP - 2922
AU - Yoshihiro KANEKO
AU - Shoji SHINODA
PY - 2002
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E85-A
IS - 12
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - December 2002
AB - A problem of obtaining an optimal file transfer of a file transmission net N is to consider how to transmit, with the minimum total cost, copies of a certain file of information from some vertices, called sources, to other vertices of N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net N. Some classes of N, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed, are known. In the characterization, we assumed that file given originally to the source remains at the source without being transmitted. In this paper, we relax the assumption to the one that a sufficient number of copies of the file are given to the source and those copies can be transmitted from the source to other vertices on N. Under this new assumption, we characterize a class of file transmission nets, on each of which a polynomial time algorithm for obtaining an optimal file transfer can be designed. A minimum spanning tree with degree constraints plays a key role in the algorithm.
ER -