Geodesic
More on the complexity of cover graphs
Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995) no. 2, pp. 269-278

Voir la notice de l'article provenant de la source Czech Digital Mathematics Library

In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
Classification : 05C85, 06A06, 68Q15, 68Q25, 68R10
Keywords: partial order; graph theory; complexity classes 
@article{CMUC_1995__36_2_a7,
     author = {Ne\v{s}et\v{r}il, Jaroslav and R\"odl, Vojt\v{e}ch},
     title = {More on the complexity of cover graphs},
     journal = {Commentationes Mathematicae Universitatis Carolinae},
     pages = {269--278},
     publisher = {mathdoc},
     volume = {36},
     number = {2},
     year = {1995},
     mrnumber = {1357529},
     zbl = {0829.06002},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/CMUC_1995__36_2_a7/}
}
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
SP  - 269
EP  - 278
VL  - 36
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CMUC_1995__36_2_a7/
LA  - en
ID  - CMUC_1995__36_2_a7
ER  - 
%0 Journal Article
%A Nešetřil, Jaroslav
%A Rödl, Vojtěch
%T More on the complexity of cover graphs
%J Commentationes Mathematicae Universitatis Carolinae
%D 1995
%P 269-278
%V 36
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CMUC_1995__36_2_a7/
%G en
%F CMUC_1995__36_2_a7
Nešetřil, Jaroslav; Rödl, Vojtěch. More on the complexity of cover graphs. Commentationes Mathematicae Universitatis Carolinae, Tome 36 (1995) no. 2, pp. 269-278. http://geodesic.mathdoc.fr/item/CMUC_1995__36_2_a7/