More on the complexity of cover graphs. (English) Zbl 0829.06002

Nešetřil, Jaroslav; Rödl, Vojtěch

Commentat. Math. Univ. Carol. 36, No. 2, 269-278 (1995).

Summary: In response to an earlier paper of ours [Order 3, 321-330 (1987; Zbl 0808.06004); Corrigendum: ibid. 10, 393 (1993; Zbl 0808.06005)], we prove that the recognition of cover graphs of finite posets is an NP-hard problem.

MSC:

06A06	Partial orders, general
68R10	Graph theory (including graph drawing) in computer science
68Q25	Analysis of algorithms and problem complexity

Keywords:

recognition of cover graphs; finite posets; NP-hard

Citations:

Zbl 0808.06004; Zbl 0808.06005