A Four-Sweep LBFS Recognition Algorithm for Interval Graphs
Peng Li, Yaokun Wu
Abstract
In their 2009 paper, Corneil et al. design a linear time
interval graph recognition algorithm based on six sweeps of
Lexicographic Breadth-First Search (LBFS) and prove its
correctness. They believe that their corresponding 5-sweep LBFS
interval graph recognition algorithm is also correct. Thanks to the
LBFS structure theory established mainly by Corneil et al., we
are able to present a 4-sweep LBFS algorithm which determines
whether or not the input graph is a unit interval graph or an interval
graph. Like the algorithm of Corneil et al., our algorithm does
not involve any complicated data structure and can be executed in
linear time.
Full Text: PDF PostScript