OPTIMUM REQUIREMENT HAMILTON CYCLE PROBLEM WITH A MONGE-LIKE PROPERTY

スポンサーリンク

概要

• 論文の詳細を見る

• Given a simple graph G with a vertex set. V and a set. of "requirements" {r_<vw>|v,w∈V}, we consider a problem to find a Hamilton cycle minimizing an objective function similar to that in the optimum requirement spanning tree (ORST) problem studied by Hu. And we show that a particular Hamilton cycle C^* which is explicitly definable is a solution to the problem when G is complete and {r_<vw>} satisfies inverse Supnick property closely related to Monge property. It is of great interest that C^* is also a solution to the symmetric traveling salesman problem with (not inverse) Supnick property. The result in this paper can be applied to the construction of ring networks with high reliability in case where the inverse Supnick property is naturally assumed.

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

著者

• Anazawa Tsutomu

  Sapporo University

関連論文

• OPTIMUM REQUIREMENT HAMILTON CYCLE PROBLEM WITH A MONGE-LIKE PROPERTY

スポンサーリンク