Loading Events

« All Events

  • This event has passed.

Yixin Cao (操宜新), Recognizing (unit) interval graphs by zigzag graph searches

Wednesday, March 17, 2021 @ 5:00 PM - 6:00 PM KST

Room B232, IBS (기초과학연구원)


Yixin Cao (操宜新)
Department of Computing, Hong Kong Polytechnic University

Corneil, Olariu, and Stewart [SODA 1998; SIAM Journal on Discrete Mathematics 2009] presented a recognition algorithm for interval graphs by six graph searches. Li and Wu [Discrete Mathematics & Theoretical Computer Science 2014] 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 Li and Wu’s algorithm, as well as a simpler implementation. We also give a self-contained presentation of the recognition algorithm of Corneil [Discrete Applied Mathematics 2004] for unit interval graphs, based on three sweeps of graph searches. Moreover, we show that two sweeps are already sufficient. Toward the proofs of the main results, we make several new structural observations that might be of independent interests.


Wednesday, March 17, 2021
5:00 PM - 6:00 PM KST
Event Category:
Event Tags:


Room B232
IBS (기초과학연구원)


O-joung Kwon (권오정)
IBS 이산수학그룹 Discrete Mathematics Group
기초과학연구원 수리및계산과학연구단 이산수학그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Discrete Mathematics Group (DIMAG)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail: dimag@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2018. All rights reserved.