More on the complexity of cover graphs
Jaroslav Nešetřil; Vojtěch Rödl
Commentationes Mathematicae Universitatis Carolinae (1995)
- Volume: 36, Issue: 2, page 269-278
- ISSN: 0010-2628
Access Full Article
top
Abstract
topHow to cite
topNešetřil, Jaroslav, and Rödl, Vojtěch. "More on the complexity of cover graphs." Commentationes Mathematicae Universitatis Carolinae 36.2 (1995): 269-278. <http://eudml.org/doc/247712>.
@article{Nešetřil1995,
abstract = {In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.},
author = {Nešetřil, Jaroslav, Rödl, Vojtěch},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {partial order; graph theory; complexity classes; recognition of cover graphs; finite posets; NP-hard},
language = {eng},
number = {2},
pages = {269-278},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {More on the complexity of cover graphs},
url = {http://eudml.org/doc/247712},
volume = {36},
year = {1995},
}
TY - JOUR
AU - Nešetřil, Jaroslav
AU - Rödl, Vojtěch
TI - More on the complexity of cover graphs
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 1995
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 36
IS - 2
SP - 269
EP - 278
AB - In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
LA - eng
KW - partial order; graph theory; complexity classes; recognition of cover graphs; finite posets; NP-hard
UR - http://eudml.org/doc/247712
ER -
References
top- Gabber O., Galil Z., Explicit construction of linear size superconcentrators, FOCS 20 (1979), J64/370. MR0598118
- Lund C., Yannakakis M., On the hardness of approximating minimization problems, 25th ACM STOC (1993), 286-293. Zbl0814.68064MR1371491
- Nešetřil J., Rödl V., Complexity of diagrams, Order 3 (1987), 321-330. MR0891379
- Nešetřil J., Rödl V., Complexity of diagrams, errata, Order 10 (1993), p. 393. MR1269275
- Sauer N., Spencer J., Edge disjoint placements of graphs, J. Comb. Th. B (1978), 295-302. (1978) MR0516262
- Brightwell G., On the complexity of Diagram Testing, Order 10 (1993), 297-303. Zbl0808.06003MR1269267
- Rödl V., Thoma L., The Complexity of Cover Graph Recognition of Some Varieties of Finite Lattices, in preparation.
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.