GRAPH MINIMAL UNCOLORABILITY IS DP-COMPLETE

被引：17

作者：

CAI, JY ^{[1
]}

MEYER, GE ^{[1
]}

机构：

[1] CORNELL UNIV, DEPT MATH, ITHACA, NY 14853 USA

来源：

SIAM JOURNAL ON COMPUTING | 1987年 / 16卷 / 02期

关键词：

D O I：

10.1137/0216022

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

MATHEMATICAL TECHNIQUES

引用

页码：259 / 277

页数：19

共 11 条

[1] EVERY PLANAR MAP IS 4 COLORABLE .1. DISCHARGING [J].

APPEL, K ;

HAKEN, W .

ILLINOIS JOURNAL OF MATHEMATICS, 1977, 21 (03) :429-490

[2] ON THE UNIQUE SATISFIABILITY PROBLEM [J].

BLASS, A ;

GUREVICH, Y .

INFORMATION AND CONTROL, 1982, 55 (1-3) :80-88

[3] On colouring the nodes of a network [J].

Brooks, RL .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1941, 37 :194-197

[4] THE CYCLIC COLORING PROBLEM AND ESTIMATION OF SPARSE HESSIAN MATRICES [J].

COLEMAN, TF ;

CAI, JY .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (02) :221-235

[5]

Garey M. R., 1976, Theoretical Computer Science, V1, P237, DOI 10.1016/0304-3975(76)90059-1

[6]

Garey MR., 1979, COMPUTERS INTRACTABI

[7]

Karp R. M., 1972, COMPLEXITY COMPUTER, P85

[8]

ORE O, 1976, 4 COLOR CONJECTURE

[9]

Papadimitriou C. H., 1985, 26th Annual Symposium on Foundations of Computer Science (Cat. No.85CH2224-4), P74, DOI 10.1109/SFCS.1985.56

[10] THE COMPLEXITY OF FACETS (AND SOME FACETS OF COMPLEXITY) [J].

PAPADIMITRIOU, CH ;

YANNAKAKIS, M .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1984, 28 (02) :244-259

← 1 2 →