article · 1993

Contiguity Orders

Vincent Bouchitte, Abdelmajid Hilali, Roland Jegou, Jean-Xavier Rampon

Cited by 0Abstract and details only

Abstract

This paper is devoted to the study of contiguity orders i.e. orders having a linear 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.

Cite this paper

APA 7

Bouchitte, V., Hilali, A., Jegou, R., & Rampon, J.-X. (1993). Contiguity Orders.

MLA 9

Bouchitte, Vincent, et al. “Contiguity Orders.” 1993.

Chicago

Bouchitte, Vincent, Abdelmajid Hilali, Roland Jegou, and Jean-Xavier Rampon. 1993. “Contiguity Orders.”

Harvard

Bouchitte, V. et al. (1993) ‘Contiguity Orders’.

BibTeX

@article{bouchitte1993contiguity,
  title = {{Contiguity Orders}},
  author = {Bouchitte, Vincent and Hilali, Abdelmajid and Jegou, Roland and Rampon, Jean-Xavier},
  year = {1993}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.