Can Transitive Orientation Make Sandwich Problems Easier?

Abstract : A graph Gs=(V,Es) is a sandwich for a pair of graphs Gt=(V,Et) and G=(V,E) if Et subset of Es and Es subset of E. A sandwich problem asks for the existence of a sandwich graph having an expected property. In a seminal paper, Golumbic et al. [Graph sandwich problems, J. Algorithms 19 (1995) 449–473] present many results on sub-families of perfect graphs. We are especially interested in comparability (resp., co-comparability) graphs because these graphs (resp., their complements) admit one or more transitive orientations (each orientation is a partially ordered set or poset). Thus, fixing the orientations of the edges of Gt and G restricts the number of possible sandwiches. We study whether adding an orientation can decrease the complexity of the problem. Two different types of problems should be considered depending on the transitivity of the orientation: the poset sandwich problems and the directed sandwich problems. The orientations added to both graphs G and Gs are transitive in the first type of problem but arbitrary for the second type.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2007, 307 (16), pp.2030-2041. 〈10.1016/j.disc.2005.12.048〉
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00189518
Contributeur : Christophe Paul <>
Soumis le : mercredi 21 novembre 2007 - 11:08:14
Dernière modification le : jeudi 24 mai 2018 - 15:59:22

Lien texte intégral

Identifiants

Citation

Michel Habib, David Kelly, Emmanuelle Lebhar, Christophe Paul. Can Transitive Orientation Make Sandwich Problems Easier?. Discrete Mathematics, Elsevier, 2007, 307 (16), pp.2030-2041. 〈10.1016/j.disc.2005.12.048〉. 〈lirmm-00189518〉

Partager

Métriques

Consultations de la notice

224