SOLVING THE LONGEST WORD-CHAIN PROBLEM
Nobuo Inui, Yuji Shinano, Yuusuke Kounoike, Yoshiyuki Kotani
2004
Abstract
The SHIRITORI game is a traditional Japanese word-chain game. This paper describes the definition of the longest SHIRITORI problem (a kind of the longest distance problem) as a problem of graph and the solution based on the integer problem (IP). This formulation requires the exponential order variables from the problem size. Against this issue, we propose a solution based on the LP-based branch-and-bound method, which solves the relaxation problems repeatedly. This method is able to calculate the longest SHIRITORI sequences for 130 thousand words dictionary within a second. In this paper, we compare the performances for the heuristic-local search and investigate the results for several conditions to explore the longest SHIRITORI problem.
DownloadPaper Citation
in Harvard Style
Inui N., Shinano Y., Kounoike Y. and Kotani Y. (2004). SOLVING THE LONGEST WORD-CHAIN PROBLEM . In Proceedings of the First International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO, ISBN 972-8865-12-0, pages 214-221. DOI: 10.5220/0001138902140221
in Bibtex Style
@conference{icinco04,
author={Nobuo Inui and Yuji Shinano and Yuusuke Kounoike and Yoshiyuki Kotani},
title={SOLVING THE LONGEST WORD-CHAIN PROBLEM},
booktitle={Proceedings of the First International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,},
year={2004},
pages={214-221},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001138902140221},
isbn={972-8865-12-0},
}
in EndNote Style
TY - CONF
JO - Proceedings of the First International Conference on Informatics in Control, Automation and Robotics - Volume 1: ICINCO,
TI - SOLVING THE LONGEST WORD-CHAIN PROBLEM
SN - 972-8865-12-0
AU - Inui N.
AU - Shinano Y.
AU - Kounoike Y.
AU - Kotani Y.
PY - 2004
SP - 214
EP - 221
DO - 10.5220/0001138902140221