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.
Type de document :
Article dans une revue
Siam Journal on Discrete Mathematics, Society for Industrial and Applied Mathematics, 2016
Liste complète des métadonnées

https://hal.inria.fr/hal-01273687
Contributeur : Michel Habib <>
Soumis le : vendredi 12 février 2016 - 18:57:10
Dernière modification le : jeudi 15 novembre 2018 - 20:27:45

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

262