On the Optimality of Forest-Type File Transfers on a File Transmission Net
Summary :
A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to transmit, with a minimum total cost, copies of a certain file of information from some vertices to others on N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net. So far, some class of N on which polynomial time algorithms for obtaining an optimal file transfer are designed has been known. In addition, if we deal with restricted file transfers, i. e. , forest-type file transfers, we can obtain an optimal 'forest-type' file transfer on more general class of N. This paper proves that for such general nets it suffices to consider forest-type file transfers in order to obtain an optimal file transfer.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.7 pp.1411-1419
- Publication Date
- 2000/07/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- PAPER
- Category
- Graphs and Networks
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
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.
Cite this
Copy
Yoshihiro KANEKO, Shoji SHINODA, "On the Optimality of Forest-Type File Transfers on a File Transmission Net" in IEICE TRANSACTIONS on Fundamentals,
vol. E83-A, no. 7, pp. 1411-1419, July 2000, doi: .
Abstract: A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to transmit, with a minimum total cost, copies of a certain file of information from some vertices to others on N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net. So far, some class of N on which polynomial time algorithms for obtaining an optimal file transfer are designed has been known. In addition, if we deal with restricted file transfers, i. e. , forest-type file transfers, we can obtain an optimal 'forest-type' file transfer on more general class of N. This paper proves that for such general nets it suffices to consider forest-type file transfers in order to obtain an optimal file transfer.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_7_1411/_p
Copy
@ARTICLE{e83-a_7_1411,
author={Yoshihiro KANEKO, Shoji SHINODA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={On the Optimality of Forest-Type File Transfers on a File Transmission Net},
year={2000},
volume={E83-A},
number={7},
pages={1411-1419},
abstract={A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to transmit, with a minimum total cost, copies of a certain file of information from some vertices to others on N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net. So far, some class of N on which polynomial time algorithms for obtaining an optimal file transfer are designed has been known. In addition, if we deal with restricted file transfers, i. e. , forest-type file transfers, we can obtain an optimal 'forest-type' file transfer on more general class of N. This paper proves that for such general nets it suffices to consider forest-type file transfers in order to obtain an optimal file transfer.},
keywords={},
doi={},
ISSN={},
month={July},}
Copy
TY - JOUR
TI - On the Optimality of Forest-Type File Transfers on a File Transmission Net
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1411
EP - 1419
AU - Yoshihiro KANEKO
AU - Shoji SHINODA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 7
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - July 2000
AB - A problem of obtaining an optimal file transfer on a file transmission net N is to consider how to transmit, with a minimum total cost, copies of a certain file of information from some vertices to others on N by the respective vertices' copy demand numbers. This problem is NP-hard for a general file transmission net. So far, some class of N on which polynomial time algorithms for obtaining an optimal file transfer are designed has been known. In addition, if we deal with restricted file transfers, i. e. , forest-type file transfers, we can obtain an optimal 'forest-type' file transfer on more general class of N. This paper proves that for such general nets it suffices to consider forest-type file transfers in order to obtain an optimal file transfer.
ER -
English
