A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network
Summary :
This paper deals with a study of a problem for finding the minimum-cost spanning tree with a response-time bound. The relation of cost and response-time is given as a monotonous decreasing and convex function. Regarding communication bandwidth as cost in an information network, this problem means a minimum-cost tree shaped routing for response-time constrained broadcasting, where any response-time from a root vertex to other vertex is less than a given time bound. This problem is proven to be NP-hard and consists of the minimum-cost assignment to a rooted tree and the minimum-cost tree finding. A nonlinear programming algorithm solves the former problem for the globally optimal solution. For the latter problem, different types of heuristic algorithms evaluate to find a near optimal solution experimentally.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.2 pp.638-646
- Publication Date
- 2001/02/01
- 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
Norihiko SHINOMIYA, Hiroshi TAMURA, Hitoshi WATANABE, "A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network" in IEICE TRANSACTIONS on Fundamentals,
vol. E84-A, no. 2, pp. 638-646, February 2001, doi: .
Abstract: This paper deals with a study of a problem for finding the minimum-cost spanning tree with a response-time bound. The relation of cost and response-time is given as a monotonous decreasing and convex function. Regarding communication bandwidth as cost in an information network, this problem means a minimum-cost tree shaped routing for response-time constrained broadcasting, where any response-time from a root vertex to other vertex is less than a given time bound. This problem is proven to be NP-hard and consists of the minimum-cost assignment to a rooted tree and the minimum-cost tree finding. A nonlinear programming algorithm solves the former problem for the globally optimal solution. For the latter problem, different types of heuristic algorithms evaluate to find a near optimal solution experimentally.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e84-a_2_638/_p
Copy
@ARTICLE{e84-a_2_638,
author={Norihiko SHINOMIYA, Hiroshi TAMURA, Hitoshi WATANABE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network},
year={2001},
volume={E84-A},
number={2},
pages={638-646},
abstract={This paper deals with a study of a problem for finding the minimum-cost spanning tree with a response-time bound. The relation of cost and response-time is given as a monotonous decreasing and convex function. Regarding communication bandwidth as cost in an information network, this problem means a minimum-cost tree shaped routing for response-time constrained broadcasting, where any response-time from a root vertex to other vertex is less than a given time bound. This problem is proven to be NP-hard and consists of the minimum-cost assignment to a rooted tree and the minimum-cost tree finding. A nonlinear programming algorithm solves the former problem for the globally optimal solution. For the latter problem, different types of heuristic algorithms evaluate to find a near optimal solution experimentally.},
keywords={},
doi={},
ISSN={},
month={February},}
Copy
TY - JOUR
TI - A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 638
EP - 646
AU - Norihiko SHINOMIYA
AU - Hiroshi TAMURA
AU - Hitoshi WATANABE
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E84-A
IS - 2
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - February 2001
AB - This paper deals with a study of a problem for finding the minimum-cost spanning tree with a response-time bound. The relation of cost and response-time is given as a monotonous decreasing and convex function. Regarding communication bandwidth as cost in an information network, this problem means a minimum-cost tree shaped routing for response-time constrained broadcasting, where any response-time from a root vertex to other vertex is less than a given time bound. This problem is proven to be NP-hard and consists of the minimum-cost assignment to a rooted tree and the minimum-cost tree finding. A nonlinear programming algorithm solves the former problem for the globally optimal solution. For the latter problem, different types of heuristic algorithms evaluate to find a near optimal solution experimentally.
ER -
English
