THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE

被引：55

作者：

JOHNSON, DS ^{[1
]}

机构：

[1] AT&T BELL LABS,MURRAY HILL,NJ 07974

来源：

JOURNAL OF ALGORITHMS | 1987年 / 8卷 / 03期

关键词：

D O I：

10.1016/0196-6774(87)90021-6

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

引用

页码：438 / 448

页数：11

共 43 条

[11] BOUNDS FOR WIDTH 2 BRANCHING PROGRAMS [J].

BORODIN, A ;

DOLEV, D ;

FICH, FE ;

PAUL, W .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :549-560

[12] GRAPH MINIMAL UNCOLORABILITY IS DP-COMPLETE [J].

CAI, JY ;

MEYER, GE .

SIAM JOURNAL ON COMPUTING, 1987, 16 (02) :259-277

[13] COVERING REGIONS BY RECTANGLES [J].

CHAIKEN, S ;

KLEITMAN, DJ ;

SAKS, M ;

SHEARER, J .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1981, 2 (04) :394-410

[14]

CONN HE, 1987, JHU8713 J HOPK U DEP

[15] CLUSTERING AND DOMINATION IN PERFECT GRAPHS [J].

CORNEIL, DG ;

PERL, Y .

DISCRETE APPLIED MATHEMATICS, 1984, 9 (01) :27-39

[16]

Dietz P.F., 1984, THESIS CORNELL U ITH

[17] DOMINATION IN PERMUTATION GRAPHS [J].

FARBER, M ;

KEIL, JM .

JOURNAL OF ALGORITHMS, 1985, 6 (03) :309-321

[18] AN ALGORITHM FOR COVERING POLYGONS WITH RECTANGLES [J].

FRANZBLAU, DS ;

KLEITMAN, DJ .

INFORMATION AND CONTROL, 1984, 63 (03) :164-189

[19] RELATIVIZATIONS OF UNAMBIGUOUS AND RANDOM POLYNOMIAL-TIME CLASSES [J].

GESKE, J ;

GROLLMANN, J .

SIAM JOURNAL ON COMPUTING, 1986, 15 (02) :511-519

[20] THE EDGE INTERSECTION GRAPHS OF PATHS IN A TREE [J].

GOLUMBIC, MC ;

JAMISON, RE .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1985, 38 (01) :8-22

← 1 2 3 4 5 →