COMPLEXITY OF COVER-PRESERVING EMBEDDINGS OF BIPARTITE ORDERS INTO BOOLEAN LATTICES

• Authors: Grzegorz Herman
• Languages of publication: PL

Abstracts

PL

We study the problem of deciding, whether a given partial order is embeddable into two consecutive layers of a Boolean lattice. Employing an equivalent condition for such em- beddability similar to the one given by J. Mittas and K. Reuter [5], we prove that the decision problem is NP-complete by showing a polynomial-time reduction from the not-all-equal variant of the Satisability problem.

Keywords

PL

• Publisher: [unknown2]
• Journal: Reports on Mathematical Logic
• Year: 2014
• Volume: 49

Dates

published

2014

online

07 - 07 - 2015

Contributors

author

Grzegorz Herman