On Poset Sandwich Problems. - LARA - Libre accès aux rapports scientifiques et techniques Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2003

On Poset Sandwich Problems.

Résumé

A graph G8 = (V,E8) is a sandwich for a pair of graph Gt=(V,E_t) and G = (V, E) si Et ⊆ E8 ⊆E. Any poset, or partially ordered set, admits a unique graph representation which is directed and transitive. In this paper we introduce the notion of sandwich poset problems inspired by former sandwich problems on comparability graphs. In particular, we are interested in series-parallel and interval posets which are subclasses of 2-dimensional posets, we describe polynomial algorithms for these two classes of poset sandwich problems and then prove that the problem of deciding the existence of a 2-dimensional sandwich poset is NP-complete.
Un graphe G8= (V, Es) est un graphe sandwich de la paire de graphes Gt=(V, Et) et G = (V, E) si Et ⊆ E8 ⊆E. Tout ordre partiel admet une représentation en graphe unique, ce graphe est orienté et transitif. Dans ce article, nous introduisons la notion de problèmes d’ordres sandwich inspirée des problèmes sandwich existants sur les graphes de comparabilité. En particulier, nous nous sommes intéressés aux ordres série-parallèles et aux ordres d’intervalle qui sont des sous-classes des ordres de dimension 2, nous décrivons des algorithmes polynomiaux pour ces deux classes de problèmes d’ordre sandwich puis nous démontrons que le problème de décider de l’existence d’un ordre sandwich de dimension 2 est NP-complet
Fichier principal
Vignette du fichier
RR2003-27.pdf (182.66 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-02101856 , version 1 (17-04-2019)

Identifiants

  • HAL Id : hal-02101856 , version 1

Citer

Michel Habib, David Kelly, Emmanuelle Lebhar, Christophe Paul. On Poset Sandwich Problems.. [Research Report] LIP RR-2003-27, Laboratoire de l'informatique du parallélisme. 2003, 2+8p. ⟨hal-02101856⟩
10 Consultations
26 Téléchargements

Partager

Gmail Facebook Twitter LinkedIn More