ある拡張された巡回セールスマン問題について

スポンサーリンク

概要

• 論文の詳細を見る

• 本稿では, クラスタ巡回セールスマン問題と呼ばれる(略してCTSP), ある拡張された巡回セールスマン問題について考える. CTSPとは, 入力としてグラフG=(V,E)とVの分割V_1,…,V_kが与えられ, 各クラスタV_i対し, 少なくともV_iに属する1つの頂点を含む, 最小コストの巡回路を見つける問題である. 本稿では, 三角不等式を満たすCTSPに対する近似解を求めることは, 少なくとも最小セットカバーに対する近似解をもとめることよりも難しいことを示す. また, クラスタの数がkのとき, CTSPがO(2^<3k>・|V|^3)時間で解けることを示す.

• 社団法人電子情報通信学会の論文
• 1997-07-11

著者

• 山崎 浩一

  電気通信大学情報工学科

• Bodlaender Hans

  Department of Computer Science, Utrecht University

• Bodlaender Hans

  Department Of Computer Science Utrecht University

• Bodlaender Hans

  Utrecht Univ. Utrecht Nld

関連論文

• k-ツリーを用いたP^k_nの新しい特徴付け
• NP完全なブール関数に対する多項式時間スライス関数について(計算モデルと計算の複雑さに関する研究)
• restricted RNLC グラフ言語の学習(計算量理論の諸相 : その基礎的研究)
• ある種のNLCグラフ文法によるグラフの集合の学習
• 量子情報理論とその応用論文小特集の発行にあたって(量子情報理論とその応用)
• Some Results for Cluster Traveling Salesperson Problem
• ある拡張された巡回セールスマン問題について
• The algorithmic aspect of "probabilistic method independent number theorem"
• ある種のグラフ問題に対するsearchとdecisionのギャップについて
• どんなグラフに対して独立点集合に対するGREEDYアルゴリズムは効率よく働くか

スポンサーリンク