ON THE COMPLEXITY OF DIAGRAM TESTING

被引：16

作者：

BRIGHTWELL, G ^{[1
]}

机构：

[1] UNIV LONDON LONDON SCH ECON & POLIT SCI,DEPT MATH,LONDON WC2A 2AE,ENGLAND

来源：

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS | 1993年 / 10卷 / 04期

关键词：

DIAGRAM; ORIENTATION; COMPLEXITY;

D O I：

10.1007/BF01108825

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In 1987, Nesetril and Rodl [4] claimed to have proved that the problem of finding whether a given graph G can be oriented as the diagram of a partial order is NP-complete. A Raw was discovered in their proof by Thostrup [11]. Nesetril and Rodl [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.

引用

页码：297 / 303

页数：7

共 11 条

[1]

Garey M.R., 1979, COMPUTERS INTRACTABI, V174

[2]

MOSESIAN KM, 1972, AKAD NAUK ARMIAN SSR, V55, P83

[3]

NESETRIL J, UNPUB ORDER

[4]

NESETRIL J, 1987, ORDER, V3, P221

[5]

ORE O, 1962, AMS C PUBL, V34

[6] BALANCED GRAPHS AND NONCOVERING GRAPHS [J].

PRETZEL, O ;

YOUNGS, D .

DISCRETE MATHEMATICS, 1991, 88 (2-3) :279-287

[7] ON REORIENTING GRAPHS BY PUSHING DOWN MAXIMAL VERTICES [J].

PRETZEL, O .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1986, 3 (02) :135-153

[8] ON GRAPHS THAT CAN BE ORIENTED AS DIAGRAMS OF ORDERED SETS [J].

PRETZEL, O .

ORDER-A JOURNAL ON THE THEORY OF ORDERED SETS AND ITS APPLICATIONS, 1985, 2 (01) :25-40

[9]

PRETZEL O, 1986, CONT MATH, V57, P103

[10]

THOSTRUP J, 1992, THESIS ODENSE U DENM

← 1 2 →