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

https://hal.inria.fr/hal-01273687
Contributor : Michel Habib <>
Submitted on : Friday, February 12, 2016 - 6:57:10 PM
Last modification on : Friday, April 19, 2019 - 11:12:03 AM

Identifiers

  • HAL Id : hal-01273687, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

318