THE NP-COMPLETENESS COLUMN - AN ONGOING GUIDE

被引：2

作者：

JOHNSON, DS ^{[1
]}

机构：

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

来源：

JOURNAL OF ALGORITHMS | 1990年 / 11卷 / 01期

关键词：

D O I：

10.1016/0196-6774(90)90035-D

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

This is the 22nd edition of an (allegedly) quarterly column that covers new developments in the theory of NP-completeness. The presentation is modeled on that used by M. R. Garey and myself in our book "Computers and Intractability: A Guide to the Theory of NP-Completeness," W. H. Freeman & Co., New York, 1979 (hereinafter referred to as "[G&J]"; previous columns will be referred to by their dates). A background equivalent to that provided by [G&J] is assumed, and, when appropriate, cross-references will be given to that book and the list of problems (NP-complete and harder) presented there. Readers who have results they would like mentioned (NP-hardness, PSPACE-hardness, polynomial-time-solvability, etc.) or open problems they would like publicized, should send them to David S. Johnson, Room 2D-150, AT&T Bell Laboratories, Murray Hill, NJ 07974 (or to dsj@research.att.com). Please include details, or at least sketches, of any new proofs; full papers are preferred. If the results are unpublished, please state explicitly that you are willing for them to be mentioned. Comments and corrections are also welcome. For more details, see the December 1981 issue of this Journal. © 1990.

引用

页码：144 / 151

页数：8