Weak-order extensions of an order

Abstract : In this paper, at first we describe a digraph representing all the weak-order extensions of a partially ordered set and algorithms for generating them. Then we present a digraph representing all of the minimal weak-order extensions of a partially ordered set. This digraph also implies generation algorithms. Finally, we prove that the number of weak-order extensions of a partially ordered set is a comparability invariant, whereas the number of minimal weak-order extensions of a partially ordered set is not a comparability invariant.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2003, 304 (1-3), pp.249-268
Liste complète des métadonnées

https://hal.inria.fr/inria-00099565
Contributeur : Jens Gustedt <>
Soumis le : mardi 26 septembre 2006 - 09:38:45
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • HAL Id : inria-00099565, version 1

Collections

Citation

Karell Bertet, Jens Gustedt, Michel Morvan. Weak-order extensions of an order. Theoretical Computer Science, Elsevier, 2003, 304 (1-3), pp.249-268. 〈inria-00099565〉

Partager

Métriques

Consultations de la notice

186