辺支配集合問題とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 辺支配集合問題の意味・解説 

辺支配集合問題

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2014/04/25 21:18 UTC 版)

辺支配集合問題(へんしはいしゅうごうもんだい)は、グラフ理論において、与えられたグラフ G(V,E) 対し、辺集合 E'⊆E のうち、任意の辺 e∈E-E' について e が E' 内の辺と端点を共有するもの(辺支配集合)のうち、最小の大きさのものを求める問題。この問題は、NP困難 であることが知られている。

各辺に重みが与えられていて、辺支配集合に含まれる辺の重みの和を最小化する問題のことを特に重み付き辺支配集合問題と呼び区別する。

重み無し辺支配集合問題については、平面グラフに対してPTASが存在することが知られている。

一般のグラフに関しては、重み無し辺支配集合問題については、任意の極大マッチングは辺支配集合なので、近似度 2 の近似アルゴリズムは、容易に得られる。重み付き辺支配集合問題については、2002年、藤戸・永持らのグループと Parekh によって独立に近似度 2 のアルゴリズムが開発された。

関連項目

外部リンク

  • MINIMUM EDGE DOMINATING SET [1]



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「辺支配集合問題」の関連用語

辺支配集合問題のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



辺支配集合問題のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの辺支配集合問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS