翻訳と辞書 Words near each other ・ 支配政党制 ・ 支配断面 ・ 支配方程式 ・ 支配権 ・ 支配的 ・ 支配者 ・ 支配者の黄昏 ・ 支配者の黄昏 TWILIGHT OF THE DARK MASTER ・ 支配逸脱現象 ・ 支配階級 ・ 支配集合問題 ・ 支釣込足 ・ 支隊 ・ 支障 ・ 支離滅裂 ・ 支飲 ・ 支麑 ・ 攰 ・ 攱 ・ 攲 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク 支配集合問題 ： ウィキペディア日本語版 支配集合問題[しはいしゅうごうもんだい] 支配集合問題（しはいしゅうごうもんだい）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ ''G''(''V'', ''E'') の頂点集合 ''V''′ (⊆ ''V'') で、''V''′ に属さない全ての頂点 ''v'' について、''v'' の隣接頂点のいずれか一つが ''V''′ に属するような ''V''′ （支配集合）のうち、最小のものを求める問題。 この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|''V''| の解を得ることができる。また、ある定数 ''c'' > 0 について、''c'' log|''V''| 近似アルゴリズムが存在しないことも示されている。 しかし、平面グラフに対しては、PTAS が存在することも知られている。 == 関連項目 == *NP完全 *アルゴリズム 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「支配集合問題」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.