A GENERALIZED OPTIMUM REQUIREMENT SPANNING TREE PROBLEM WITH A MONGE-LIKE PROPERTY

スポンサーリンク

概要

• 論文の詳細を見る

• We consider a generalized optimum requirement spanning tree problem (GORST problem) which is an extension of the problem studied by Hu. In the GORST problem, the degrees of vertices are restricted and the objective function is generalized. We will show that a particular tree T^*, which is obtained by a sort of greedy algorithm but is explicitly definable, is a solution to the GORST problem when a condition similar to the Monge property is satisfied. Also, we will define a problem of finding a tree network which minimizes the probability that a request of communication is not realized when the network has k failures (called a "k-failure problem"), and show that T^* is an explicit solution to the k-failure problem for any k when the maximum degree constraint is imposed and the Monge-like property is satisfied.

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• Anazawa T

  Sapporo Univ.

• Anazawa Tsutomu

  Department of Industry and Information, Sapporo University

関連論文

• A GENERALIZED OPTIMUM REQUIREMENT SPANNING TREE PROBLEM WITH A MONGE-LIKE PROPERTY

スポンサーリンク