擬似モンジュ性を伴う最適要求ハミルトン閉路問題

スポンサーリンク

概要

• 論文の詳細を見る

• 本論文では,節集合がVの単純グラフGと「要求」の集合{r_>υω<|υ,ω∈V}が与えられたとき,Huが提示した最適要求木問題の目的関数に似た関数を最小化するハミルトン閉路を求める問題を考察する.そして,Gが完全かつ{r_>υω<}がモンジュ性と関係の深い逆スープニック性を満たすとき,ある特殊なハミルトン閉路C^*(それは陽に定義可能)が最適解であることを示す.興味深いことに,このC^*は(逆でない)スープニック性を伴う対称巡回セールスマン問題の最適解でもある.さらに本論文では,リング型ネットワークの構築において逆スープニック性を自然に仮定できる場合があることと,その場合はC^*が最適なリング型ネットワークとなることを示す.

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

著者

• 穴沢 務

  札幌大学

関連論文

• 擬似モンジュ性を伴う最適要求ハミルトン閉路問題
• Optimum Requirement Cycle with a Monge-like Property
• Lexicographically Optimum Traffic Trees with Maximum Degree Constraints
• A Generalized Optimum Requirement Spanning Tree Problem with a Monge-like Property
• Optimum Tree Networks for Single or Double Failure

スポンサーリンク