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

Grzegorz Herman

Abstrakt
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 Satis ability problem.
References

[1] T.J. Schaefer, The complexity of satisfiabilitproblems, Conference Record of the Tenth Annual ACM Symposium on Theory of Computing, 1978, pp. 216–226.

[2] G.Cybenko, D. W. Krumme, K. N. Venkataraman, Fixed hypercube embedding, Information Processing Letters 25 (1987), 35–39.

[3] B. Monien, H. Sudborough, Embedding one interconnection network in another, Computing Suppl. 7 (1990), 257–282.

[4] M. Wild, Cover-preserving embeddings into boolean lattices, Order (1992), 209–232.

[5] J. Mitas, K. Reuter, Cover-Preserving Embeddings of Bipartite Orders into Boolean Lattices, Theoretical Computer Science 175 (1997), 337–347.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.