FIT2019 第18回情報科学技術フォーラム 開催日：2019年9月3日（火）～5日（木）　会場：岡山大学津島キャンパス
抄録
CA-006
SATソルバを用いたC1P分割問題の解法
◎原田崇司・竹内聖悟（高知工科大）
0-1行列の列を並び替えることにより各行の1を連続させられるとき，その0-1行列はConsecutive Ones Property (C1P) を満たす．0-1行列がC1Pを満たすかは行列サイズの多項式時間で判定可能である．けれどもC1Pを満たさない0-1行列MをC!Pを満たす部分行列M1, M2へと分割できるかを判定する問題はNP完全である．本稿では，0-1行列MをC1Pを満たす部分行列M1, M2, ..., Mkへと分割できるかを判定するSATソルバを用いた解法を提案する．