すいません。
半角カタカナで濁点、-は無視してかまいません。
総当たりでしりとりを行うプログラムをつくったのですが、
単語数が多くなるとプログラムが処理しきれなくなったところ、
整数計画法を用いて解けといわれたので。

ttp://auemath.aichi-edu.ac.jp/~ykhashi/semi/2010note/08_issey_final.pdf
にのっているアルゴリズムでよさそうなのですが、自分だと実装できなくて。
説明不足で済みません。