For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network
Norihiko SHINOMIYA Hiroshi TAMURA Hitoshi WATANABE
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2001/02/01
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
graph theory, information network, minimum-cost tree, response time, NP-complete,
Full Text: PDF(374.6KB)>>
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.