Yixin Cao (操宜新), Recognizing (unit) interval graphs by zigzag graph searches
Room B232 IBS (기초과학연구원)Corneil, Olariu, and Stewart presented a recognition algorithm for interval graphs by six graph searches. Li and Wu simplified it to only four. The great simplicity of the latter algorithm is however eclipsed by the complicated and long proofs. The main purpose of this paper is to present a new and significantly shorter proof for …