A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network

Hiroshi TAMURA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E84-A    No.2    pp.638-646
Publication Date: 2001/02/01
Online ISSN: 
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>>
Buy this Article

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.