Complexity of Cover-Preserving Embeddings of Bipartite Orders Into Boolean Lattices
cytuj
pobierz pliki
RIS BIB ENDNOTEChoose format
RIS BIB ENDNOTEPublication date: 21.10.2014
Reports on Mathematical Logic, 2014, Number 49, pp. 99-117
https://doi.org/10.4467/20842589RM.14.006.2276Authors
Complexity of Cover-Preserving Embeddings of Bipartite Orders Into Boolean Lattices
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 Satisfiability problem.
[1] T.J. Schaefer, The complexity of satisfiability problems, 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 9 (1992), 209–232.
[5] J. Mitas, K. Reuter, Cover-Preserving Embeddings of Bipartite Orders into Boolean Lattices, Theoretical Computer Science 175 (1997), 337–347.
Information: Reports on Mathematical Logic, 2014, Number 49, pp. 99-117
Article type: Original article
Department of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University
Published at: 21.10.2014
Article status: Open
Licence: None
Percentage share of authors:
Article corrections:
-Publication languages:
EnglishView count: 1967
Number of downloads: 1204