More on the complexity of cover graphs

Previous | Up | Next

Article

More on the complexity of cover graphs. (English). Commentationes Mathematicae Universitatis Carolinae, vol. 36 (1995), issue 2, pp. 269-278

MSC: 05C85, 06A06, 68Q15, 68Q25, 68R10 | MR 1357529 | Zbl 0829.06002

Keywords:
partial order; graph theory; complexity classes

Summary:
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.

References:

[1] Gabber O., Galil Z.: Explicit construction of linear size superconcentrators. FOCS 20 (1979), J64/370. MR 0598118

[2] Lund C., Yannakakis M.: On the hardness of approximating minimization problems. 25th ACM STOC (1993), 286-293. MR 1371491 | Zbl 0814.68064

[3] Nešetřil J., Rödl V.: Complexity of diagrams. Order 3 (1987), 321-330. MR 0891379

[4] Nešetřil J., Rödl V.: Complexity of diagrams. errata, Order 10 (1993), p. 393. MR 1269275

[5] Sauer N., Spencer J.: Edge disjoint placements of graphs. J. Comb. Th. B (1978), 295-302. MR 0516262

[6] Brightwell G.: On the complexity of Diagram Testing. Order 10 (1993), 297-303. MR 1269267 | Zbl 0808.06003

[7] Rödl V., Thoma L.: The Complexity of Cover Graph Recognition of Some Varieties of Finite Lattices. in preparation.

Partner of