Property |
Value |
dbo:abstract
|
- 計算量理論において、最小のクリーク被覆(クリークひふく、英: clique cover)を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はの1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"(「組合せ論的問題間の還元可能性」)に示されている。 クリーク被覆問題(クリーク分割問題と呼ぶこともある)とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ G の k-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき G の k-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する(各集合にそれぞれ別の1つの色を塗ることで k-彩色ができたことになる)。 この問題と関連して、問題は与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 (ja)
- 計算量理論において、最小のクリーク被覆(クリークひふく、英: clique cover)を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はの1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"(「組合せ論的問題間の還元可能性」)に示されている。 クリーク被覆問題(クリーク分割問題と呼ぶこともある)とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ G の k-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき G の k-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する(各集合にそれぞれ別の1つの色を塗ることで k-彩色ができたことになる)。 この問題と関連して、問題は与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 (ja)
|
dbo:wikiPageExternalLink
| |
dbo:wikiPageID
| |
dbo:wikiPageLength
|
- 1705 (xsd:nonNegativeInteger)
|
dbo:wikiPageRevisionID
| |
dbo:wikiPageWikiLink
| |
prop-ja:wikiPageUsesTemplate
| |
dct:subject
| |
rdfs:comment
|
- 計算量理論において、最小のクリーク被覆(クリークひふく、英: clique cover)を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はの1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"(「組合せ論的問題間の還元可能性」)に示されている。 クリーク被覆問題(クリーク分割問題と呼ぶこともある)とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ G の k-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき G の k-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する(各集合にそれぞれ別の1つの色を塗ることで k-彩色ができたことになる)。 この問題と関連して、問題は与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 (ja)
- 計算量理論において、最小のクリーク被覆(クリークひふく、英: clique cover)を求めることは、グラフ理論的NP完全問題である。クリーク被覆問題はの1つで、そのNP完全性は1972年の論文 "Reducibility Among Combinatorial Problems"(「組合せ論的問題間の還元可能性」)に示されている。 クリーク被覆問題(クリーク分割問題と呼ぶこともある)とは、与えられたグラフの頂点集合を k-個のクリークへ分割できるかを決定する問題である。頂点集合の k-個の集合への分割が与えられたとき、その各集合がクリークを成すかは多項式時間で判定することができるから、クリーク被覆問題はNPに属する。そのNP完全性はグラフの k-彩色可能性からの帰着である。これを見るには、まずグラフ G の k-彩色可能性をその補グラフ G′ に関する事実に翻訳すればよい。このとき G の k-個のクリークへの分割は G′ の k-個の独立集合への分割を求めることに対応する(各集合にそれぞれ別の1つの色を塗ることで k-彩色ができたことになる)。 この問題と関連して、問題は与えられたグラフの辺をすべて含むようなクリークの集合を考えるもので、これもまたNP完全問題である。 (ja)
|
rdfs:label
|
- 最小クリーク被覆問題 (ja)
- 最小クリーク被覆問題 (ja)
|
owl:sameAs
| |
prov:wasDerivedFrom
| |
foaf:isPrimaryTopicOf
| |
is dbo:wikiPageDisambiguates
of | |
is dbo:wikiPageWikiLink
of | |
is owl:sameAs
of | |
is foaf:primaryTopic
of | |