THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE

被引:210
作者
JOHNSON, DS [1 ]
机构
[1] AT&T BELL LABS, MURRAY HILL, NJ 07974 USA
来源
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 1985年 / 6卷 / 03期
关键词
D O I
10.1016/0196-6774(85)90012-4
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
引用
收藏
页码:434 / 451
页数:18
相关论文
共 83 条
[61]   ISOMORPHISM OF K-CONTRACTIBLE GRAPHS - A GENERALIZATION OF BOUNDED VALENCE AND BOUNDED GENUS [J].
MILLER, GL .
INFORMATION AND CONTROL, 1983, 56 (1-2) :1-20
[62]  
MILLER GL, 1980, 12TH P ACM S THEOR C, P225
[63]   ON MAXIMAL INDEPENDENT SETS OF VERTICES IN CLAW-FREE GRAPHS [J].
MINTY, GJ .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1980, 28 (03) :284-304
[64]  
MONIEN B, 1981, 13TH P ANN ACM STOC, P207
[65]  
MONMA CL, 1985, UNPUB INTERSECTION G
[66]   AN O(N2) ALGORITHM FOR COLORING PROPER CIRCULAR ARC GRAPHS [J].
ORLIN, JB ;
BONUCCELLI, MA ;
BOVET, DP .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1981, 2 (02) :88-93
[67]  
PROSKUROWSKI A, 1982, UOCISTR825 U OR DEP
[68]   DYNAMIC-PROGRAMMING ALGORITHMS FOR RECOGNIZING SMALL-BANDWIDTH GRAPHS IN POLYNOMIAL-TIME [J].
SAXE, JB .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1980, 1 (04) :363-369
[70]  
SCHAFFER A, 1985, COMMUNICATION