Dominating setとは？わかりやすく解説

支配集合問題（しはいしゅうごうもんだい、英: dominating set）は、グラフ理論における有名なNP困難な問題の一つ。与えられたグラフ G(V, E) の頂点集合 V′ (⊆ V) で、V′ に属さない全ての頂点 v について、v の隣接頂点のいずれか一つが V′ に属するような V′ （支配集合）のうち、最小のものを求める問題。

この問題は、集合被覆問題に含まれるため、集合被覆問題への近似アルゴリズムを適用することで近似度 1 + log|V| の解を得ることができる。また、ある定数 c > 0 について、c log|V| 近似アルゴリズムが存在しないことも示されている。

しかし、平面グラフに対しては、PTAS が存在することも知られている。

外部リンク

MINIMUM DOMINATING SET


	All text is available under the terms of the GNU Free Documentation License. この記事は、ウィキペディアの支配集合問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
TANAKA Corpus	Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います： Creative Commons Attribution (CC-BY) 2.0 France.
京大-NICT 日英中基本文データ	この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
	Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
	Copyright © Benesse Holdings, Inc. All rights reserved.
	Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
	日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved. WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
	Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved. 「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
	This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

Dominating setとは？わかりやすく解説

支配集合問題

関連項目

外部リンク

「Dominating set」の例文・使い方・用例・文例

「Dominating set」の関連用語

Dominating setとは？ わかりやすく解説

支配集合問題

関連項目

外部リンク

「Dominating set」の例文・使い方・用例・文例

「Dominating set」の関連用語

Dominating setとは？わかりやすく解説