Skip to Main content Skip to Navigation

On Poset Sandwich Problems.

Abstract : 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.
Document type :
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download
Contributor : Colette Orange Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:08:12 AM
Last modification on : Saturday, September 11, 2021 - 3:19:18 AM


Files produced by the author(s)


  • HAL Id : hal-02101856, version 1



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⟩



Les métriques sont temporairement indisponibles