どんなグラフに対して独立点集合に対するGREEDYアルゴリズムは効率よく働くか

スポンサーリンク

概要

• 論文の詳細を見る

• 本稿では,独立点集合に対するGREEDYアルゴリズムについで考える.ある与えられたグラフに対し,GREEDYアルゴリズムが常にある近似解を出力するかどうかを判定する問題は,coNP完全であることを示す.また,与えられたグラフに対し,ある適当な順序でGREEDYアルゴリズムを行った場合,ある近似解を出力するかを判定する問題は,DP困難であることを示す.

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

著者

• Bodlaender Hans

  Department Of Computer Science Utrecht University

• Yamazaki K

  Univ. Electro‐communications Chofu‐shi Jpn

• Thilikos Dimitrios

  Department of Computer Science, Utrecht University

• Yamazaki Koichi

  Department of Computer Science, Utrecht University

• Thilikos Dimitrios

  Department Of Computer Science Utrecht University

• Yamazaki Koichi

  Department Of Computer Science Gunma University

関連論文

• Some Results for Cluster Traveling Salesperson Problem
• ある拡張された巡回セールスマン問題について
• どんなグラフに対して独立点集合に対するGREEDYアルゴリズムは効率よく働くか
• Special Section on Foundations of Computer Science -Mathematical Foundations and Applications of Computer Science and Algorithms-

スポンサーリンク