More on the complexity of cover graphs
Nešetřil, Jaroslav ; Rödl, Vojtěch
Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995), p. 269-278 / Harvested from Czech Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 1995-01-01
Classification:  05C85,  06A06,  68Q15,  68Q25,  68R10 
@article{118756,
     author = {Jaroslav Ne\v set\v ril and Vojt\v ech R\"odl},
     title = {More on the complexity of cover graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     volume = {36},
     year = {1995},
     pages = {269-278},
     zbl = {0829.06002},
     mrnumber = {1357529},
     language = {en},
     url = {http://dml.mathdoc.fr/item/118756}
}

Nešetřil, Jaroslav; Rödl, Vojtěch. More on the complexity of cover graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995) pp. 269-278. http://gdmltest.u-ga.fr/item/118756/

Gabber O.; Galil Z. Explicit construction of linear size superconcentrators, FOCS 20 (1979), J64/370. | MR 0598118

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

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

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

Sauer N.; Spencer J. Edge disjoint placements of graphs, J. Comb. Th. B (1978), 295-302. (1978) | MR 0516262

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

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