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 :
Reports
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101856
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:08:12 AM
Last modification on : Sunday, May 19, 2019 - 1:20:46 AM

File

RR2003-27.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101856, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

2

Files downloads

8