Skip to Main content Skip to Navigation
Journal articles

On the power of graph searching for cocomparability graphs

Abstract : In this paper we study how graph searching on a cocomparability graph G can be used to pro- duce cocomp orderings, (i.e., orderings that are linear extensions of some transitive orientation of 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. Keywords: Cocomparability graphs, comparability graphs, partial orders, linear extensions, graph algorithms, classical graph searches, lexicographic depth first search (LDFS), minimum path cover problem, recognition of permutation graphs.
Complete list of metadatas
Contributor : Michel Habib <>
Submitted on : Friday, February 12, 2016 - 6:57:10 PM
Last modification on : Friday, April 10, 2020 - 5:20:01 PM


  • HAL Id : hal-01273687, version 1



Derek G. Corneil, Jérémie Dusart, Michel Habib, Ekkerhard Köhler. On the power of graph searching for cocomparability graphs. SIAM Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016. ⟨hal-01273687⟩



Record views