PL EN


Preferences help
enabled [disable] Abstract
Number of results
2014 | 49 |
Article title

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

Authors
Content
Title variants
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
Year
Volume
49
Physical description
Dates
published
2014
online
07 - 07 - 2015
Contributors
References
Document Type
Publication order reference
Identifiers
YADDA identifier
bwmeta1.element.ojs-issn-2084-2589-year-2014-volume-49-article-2922
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.