講演抄録/キーワード |
講演名 |
2007-12-19 13:50
集合打問題と接続行列に関する一考察 ○小林邦勝(山形大) ISEC2007-120 |
抄録 |
(和) |
NP完全問題である集合打問題の解法について検討する。集合打問題における集合の列とそれら集合の各要素を、グラフGの頂点と辺に対応させることにより、集合打問題はグラフGの接続行列Mで表される。接続行列Mの任意の2つの列ベクトルの内積が0になるとき、この2つの列ベクトルを互いに素と呼ぶことにすると、集合打問題に解があるか否かの判定は、互いに素な幾つかの列ベクトルの和で成分がすべて1の列ベクトルを生成できるか否かの判定と同等になる。本文では、グラフGの頂点数をn、辺の数をtとするとき、集合打問題に解が存在するか否かをnとtの多項式時間で判定するアルゴリズムを提案する。 |
(英) |
We examine a solution of hitting set problem. By using incidence matrix M of graph G, we can decide whether hitting set problem has a solution or not efficiently. |
キーワード |
(和) |
集合打問題 / NP完全 / 接続行列 / NP=P / / / / |
(英) |
hitting set problem / NP complete / incidence matrix / NP=P / / / / |
文献情報 |
信学技報, vol. 107, no. 397, ISEC2007-120, pp. 55-58, 2007年12月. |
資料番号 |
ISEC2007-120 |
発行日 |
2007-12-12 (ISEC) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
ISEC2007-120 |