Contiguity orders

Abstract : This paper is devoted to the study of contiguity orders i.e. orders having a linear extension extension L such that all upper (or lower) cover sets are intervals of L. This new class is a strict generalization of both interval orders and N-free orders and is linearly recognizable. It is proved that computing the number of contiguity extensions is #P-complete and that the dimension of height one contiguity orders is polynomially tractable. Moreover the membership is a comparability invariant on bi-contiguity orders. Finally for strong-contiguity orders the calculation of the dimension is NP-complete.
Type de document :
Rapport
[Research Report] RR-1970, INRIA. 1993
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00074703
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 16:06:35
Dernière modification le : mardi 16 janvier 2018 - 15:51:08
Document(s) archivé(s) le : lundi 5 avril 2010 - 00:13:37

Fichiers

Identifiants

  • HAL Id : inria-00074703, version 1

Citation

Vincent Bouchitté, Abdelmajid Hilali, Roland Jégou, Jean-Xavier Rampon. Contiguity orders. [Research Report] RR-1970, INRIA. 1993. 〈inria-00074703〉

Partager

Métriques

Consultations de la notice

169

Téléchargements de fichiers

117