Complexity of cover - preserving embeddings of bipartite orders into boolean lattices

• Autorzy: Herman G.

Identyfikatory

DOI

10.4467/20842589RM.14.006.2276

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Boolean lattice; NP-complete; polynomial-time reduction; variant of the Satisfiability problem

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2014
• Tom: Vol. 49
• Strony: 99--117
• Opis fizyczny: Bibliogr. 5 poz., rys.

Twórcy

autor

Herman G.

• Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, ul. St. Łojasiewicza 6, 30-348 Krakow, Poland

Bibliografia

• [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.