On the complexity of diagram testing |
| |
Authors: | Graham Brightwell |
| |
Affiliation: | (1) Department of Mathematics, London School of Economics and Political Science, Houghton Street, WC2A 2AE London, UK |
| |
Abstract: | In 1987, Neetil and Rödl [4] claimed to have proved that the problem of finding whether a given graphG can be oriented as the diagram of a partial order is NP-complete. A flaw was discovered in their proof by Thostrup [11]. Neetil and Rödl [5] have since corrected the proof, but the new version is rather complex. We give a simpler and more elementary proof, using a completely different approach. |
| |
Keywords: | 06A06 68Q25 |
本文献已被 SpringerLink 等数据库收录! |
|