论文标题
通过锯齿形图识别（单位）间隔图搜索
Recognizing (Unit) Interval Graphs by Zigzag Graph Searches
论文作者
论文摘要
Corneil，Olariu和Stewart [Soda 1998; SIAM关于离散数学2009的日记]通过六个图形搜索提出了一种间隔图的识别算法。 Li和Wu [离散数学\＆理论计算机科学2014]将其简化为四个。然而，后一种算法的极其简单被复杂而长的证据所黯然失色。本文的主要目的是为Li和Wu的算法提供一个新的且明显的简短证明，以及更简单的实现。我们还基于三个图形搜索的三个扫描，对Corneil的识别算法进行了更简单的解释[离散应用数学2004]。此外，我们表明两次扫描已经足够了。为了证明主要结果，我们进行了几种可能具有独立利益的新结构观察。
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 short proof for Li and Wu's algorithm, as well as a simpler implementation. We also give a self-contained simpler interpretation 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.
