講演抄録/キーワード |
講演名 |
2019-10-25 15:05
Circ1P分割問題の計算複雑さと解法 ○竹内聖悟・原田崇司(高知工科大) COMP2019-25 |
抄録 |
(和) |
0-1行列の列を並び替えることにより各行の1または0を連続させられるとき,その0-1行列はCircular Ones Property (Circ1P) を満たす.0-1行列がCirc1Pを満たすかは行列サイズの多項式時間で判定可能である.本稿では, Circ1Pを満たさない0-1行列をCirc1Pを満たす部分行列へと分割できるかを判定する問題がNP完全であることを示し, その問題に対するアルゴリズムを提案する. |
(英) |
0-1 matrix satisfies Circular Ones Property (Circ1P) when 1 or 0 in each row can be continued by reordering the columns of the matrix. Whether the 0-1 matrix satisfies Circ1P can be determined by polynomial time of the matrix size. In this paper, we show that the problem of determining whether a 0-1 matrix which does not satisfy Circ1P can be divided into submatrices which satisfy Circ1P is NP-complete and propose an algorithm for the problem. |
キーワード |
(和) |
0-1行列 / Circular Ones Property / / / / / / |
(英) |
0-1 matrix / Circular Ones Property / / / / / / |
文献情報 |
信学技報, vol. 119, no. 249, COMP2019-25, pp. 53-56, 2019年10月. |
資料番号 |
COMP2019-25 |
発行日 |
2019-10-18 (COMP) |
ISSN |
Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2019-25 |