Contiguity orders

Vincent Bouchitté (1) , Abdelmajid Hilali (2) , Roland Jégou (3) , Jean-Xavier Rampon (4)

1 ENS de Lyon - École normale supérieure de Lyon
2 UCBL - Université Claude Bernard Lyon 1
3 Départment d'Informatique Appliquée [Saint Etienne]
4 PAMPA - Models and Tools for Programming Distributed Parallel Architectures

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.

Domaines: Autre [cs.OH]

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