Aucbvax.5264
fa.arpa-bboard
utzoo!decvax!ucbvax!PINTER@MIT-ML
Fri Nov 20 05:58:38 1981
Renewed call for NP-Completeness Results
From: PINTER@MIT-ML
David Johnson from Bell Labs, coauthor of [G&J], has asked me to communicate
the following request to the Computer Science community:


               Renewed  Call  for NP-Completeness  Results

       In order to provide a clearinghouse for the continuing flood of
NP-completeness results (and postpone the necessity of preparing a new edition
of [G&J] until that flood subsides) I am going to be writing a quarterly column
on NP-completeness, to appear in the "Journal of Algorithms", which will act as
a continuing update for the list in [G&J], as well as a forum for open
problems.

       Anyone having results or open problem they wish mentioned in the column
should send them to me at the address(es) below. For new results (NP-hardness
proofs, polynomial time algorithms for special cases, etc.) the types of
submissions are, in order of preference:
   (1) References to published papers containing results not already cited in
       [G&J]. Please include a brief description of the nature of the results,
       and the precise place in the paper where the results are presented.
       Include reprint if possible.
   (2) Technical reports or unpublished manuscripts containing results as
       above. Again, please include a brief description and a precise
       location.
   (3) Informal notes on new results, stating the claimed results precisely
       and giving at least some indication of the proof.
   (4) Rumors, together with some idea of how they might be tracked down.
In the case of unpublished results, please state explicitly that you would like
the results mentioned in the column.

       Proposed open problems should be described precisely, and should be
accompanied by an explanation of the  motivation behind them, including, where
possible, references to relevant published works. In addition, suggestions,
comments, and corrections are welcome.

       Please send all material to     David S. Johnson
                                       Room  2C-355
                                       Bell Laboratories
                                       Murray Hill, NJ 07974
       or use one of the following addresses on the UNIX network:
                                       allegra!alice!dsj
                                       research!dsj

[G&J] M.R. Garey and D.S. Johnson, "Computers and Intractability: A Guide to
the Theory of NP-Completeness", W.H. Freeman & Company, San-Francisco, 1979.

-----------------------------------------------------------------
gopher://quux.org/ conversion by John Goerzen <[email protected]>
of http://communication.ucsd.edu/A-News/


This Usenet Oldnews Archive
article may be copied and distributed freely, provided:

1. There is no money collected for the text(s) of the articles.

2. The following notice remains appended to each copy:

The Usenet Oldnews Archive: Compilation Copyright (C) 1981, 1996
Bruce Jones, Henry Spencer, David Wiseman.

You are viewing proxied material from gopher.quux.org. The copyright of proxied material belongs to its original authors. Any comments or complaints in relation to proxied material should be directed to the original authors of the content concerned. Please see the disclaimer for more details.