| Title:
|
More on the complexity of cover graphs (English) |
| Author:
|
Nešetřil, Jaroslav |
| Author:
|
Rödl, Vojtěch |
| Language:
|
English |
| Journal:
|
Commentationes Mathematicae Universitatis Carolinae |
| ISSN:
|
0010-2628 (print) |
| ISSN:
|
1213-7243 (online) |
| Volume:
|
36 |
| Issue:
|
2 |
| Year:
|
1995 |
| Pages:
|
269-278 |
| . |
| Category:
|
math |
| . |
| Summary:
|
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem. (English) |
| Keyword:
|
partial order |
| Keyword:
|
graph theory |
| Keyword:
|
complexity classes |
| MSC:
|
05C85 |
| MSC:
|
06A06 |
| MSC:
|
68Q15 |
| MSC:
|
68Q25 |
| MSC:
|
68R10 |
| idZBL:
|
Zbl 0829.06002 |
| idMR:
|
MR1357529 |
| . |
| Date available:
|
2009-01-08T18:17:53Z |
| Last updated:
|
2012-04-30 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/118756 |
| . |
| Reference:
|
[1] Gabber O., Galil Z.: Explicit construction of linear size superconcentrators.FOCS 20 (1979), J64/370. MR 0598118 |
| Reference:
|
[2] Lund C., Yannakakis M.: On the hardness of approximating minimization problems.25th ACM STOC (1993), 286-293. Zbl 0814.68064, MR 1371491 |
| Reference:
|
[3] Nešetřil J., Rödl V.: Complexity of diagrams.Order 3 (1987), 321-330. MR 0891379 |
| Reference:
|
[4] Nešetřil J., Rödl V.: Complexity of diagrams.errata, Order 10 (1993), p. 393. MR 1269275 |
| Reference:
|
[5] Sauer N., Spencer J.: Edge disjoint placements of graphs.J. Comb. Th. B (1978), 295-302. MR 0516262 |
| Reference:
|
[6] Brightwell G.: On the complexity of Diagram Testing.Order 10 (1993), 297-303. Zbl 0808.06003, MR 1269267 |
| Reference:
|
[7] Rödl V., Thoma L.: The Complexity of Cover Graph Recognition of Some Varieties of Finite Lattices.in preparation. |
| . |
