
For FullText 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 MinimumCost Tree Problem with ResponseTime Bound in Information Network
Norihiko SHINOMIYA Hiroshi TAMURA Hitoshi WATANABE
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E84A
No.2
pp.638646 Publication Date: 2001/02/01 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: graph theory, information network, minimumcost tree, response time, NPcomplete,
Full Text: PDF>>
Summary:
This paper deals with a study of a problem for finding the minimumcost spanning tree with a responsetime bound. The relation of cost and responsetime is given as a monotonous decreasing and convex function. Regarding communication bandwidth as cost in an information network, this problem means a minimumcost tree shaped routing for responsetime constrained broadcasting, where any responsetime from a root vertex to other vertex is less than a given time bound. This problem is proven to be NPhard and consists of the minimumcost assignment to a rooted tree and the minimumcost 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.

