The search functionality is under construction.

The search functionality is under construction.

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.

- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E85-A No.12 pp.2913-2922

- Publication Date
- 2002/12/01

- Publicized

- Online ISSN

- DOI

- Type of Manuscript
- PAPER

- Category
- Graphs and Networks

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.

Copy

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

Copy

@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},}

Copy

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 -