This corrigendum corrects errors found by Jérémie Dusart in the proof of correctness of the algorithms in [D. G. Corneil, B. Dalton, and M. Habib, SIAM J. Comput., 42 (2013), pp. 792--807]; there are no changes in the algorithms themselves.

In this paper we study how graph searching on a cocomparability graph $G$ can be used to produce cocomp orderings (i.e., orderings that are linear extensions of some transitive orientation of $\overline{G}$) that yield simple algorithms for various intractable problems in general. Such techniques have been used to find a simple certifying algorithm for the minimum path cover problem. In particular we present a characterization of the searches that preserve cocomp orderings when used as a “$^+$” sweep. This allows us to present a toolbox of different graph searches and a framework to solve various problems on cocomparability graphs. We illustrate these techniques by describing a very simple certifying algorithm for the maximum independent set problem as well as a simple permutation graph recognition algorithm.