辺支配集合問題のソースを表示
←
辺支配集合問題
移動先:
案内
、
検索
あなたには「このページの編集」を行う権限がありません。理由は以下の通りです:
要求した操作を行うことは許可されていません。
このページのソースの閲覧やコピーができます。
'''辺支配集合問題'''(へんしはいしゅうごうもんだい)は、[[グラフ理論]]において、与えられたグラフ G(V,E) 対し、辺集合 E'⊆E のうち、任意の辺 e∈E-E' について e が E' 内の辺と端点を共有するもの(辺支配集合)のうち、最小の大きさのものを求める問題。この問題は、[[NP困難]] であることが知られている。 各辺に重みが与えられていて、辺支配集合に含まれる辺の重みの和を最小化する問題のことを特に'''重み付き辺支配集合問題'''と呼び区別する。 重み無し辺支配集合問題については、[[平面グラフ]]に対して[[PTAS]]が存在することが知られている。 一般のグラフに関しては、重み無し辺支配集合問題については、任意の[[極大マッチング]]は辺支配集合なので、[[近似度]] 2 の[[近似アルゴリズム]]は、容易に得られる。重み付き辺支配集合問題については、[[2002年]]、藤戸・永持らのグループと Parekh によって独立に近似度 2 の[[アルゴリズム]]が開発された。 ==関連項目== *[[NP完全]] *[[支配集合問題]] ==外部リンク== *MINIMUM EDGE DOMINATING SET [http://www.nada.kth.se/~viggo/wwwcompendium/node13.html] {{デフォルトソート:へんしはいしゆうこうもんたい}} [[category:グラフ理論]] [[Category:数学に関する記事]]
辺支配集合問題
に戻る。
案内メニュー
個人用ツール
ログイン
名前空間
ページ
議論
変種
表示
閲覧
ソースを表示
履歴表示
その他
検索
案内
メインページ
コミュニティ・ポータル
最近の出来事
新しいページ
最近の更新
おまかせ表示
sandbox
commonsupload
ヘルプ
ヘルプ
井戸端
notice
bugreportspage
sitesupport
ウィキペディアに関するお問い合わせ
ツール
リンク元
関連ページの更新状況
特別ページ
ページ情報