Jaroslav Ne\v{s}et\v{r}il, Vojt\v{e}ch R\"{o}dl

Jaroslav Ne\v{s}et\v{r}il, Vojt\v{e}ch R\"{o}dl
More on the complexity of cover graphs

Comment.Math.Univ.Carolinae 36,2 (1995) 271-280.

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

Keywords: partial order, graph theory, complexity classes
AMS Subject Classification: 06A06, 68R10, 68Q15