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

スポンサーリンク

概要

• 論文の詳細を見る

• 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.

• 社団法人電子情報通信学会の論文
• 2001-02-01

著者

• TAMURA Hiroshi

  the Department of Cardiology, Juntendo University Izunagaoka Hospital

• Shinomiya Norihiko

  The Faculty Of Engineering Soka University:(present Address)the Network Systems Laboratories Fujitsu

• WATANABE Hitoshi

  the Faculty of Engineering, Soka University

• Watanabe Hitoshi

  The Faculty Of Engineering Soka University

• Tamura Hiroshi

  The Department Of Information And Electronics Engineering Niigata Institute Of Technology

関連論文

• Superior Vena Cava Syndrome Due to Fibrosing Mediastinitis Histologically Identical to Xanthogranulomatous Pyelonephritis
• Superior Vena Cava Syndrome Due to Fibrosing Mediastinitis Histologically Identical to Xanthogranulomatous Pyelonephritis
• A Study of Minimum-Cost Tree Problem with Response-Time Bound in Information Network
• A Basic Theory of Information Network (Special Section on the 5th Karuizawa Workshop on Circuits and Systems)

スポンサーリンク