Text File

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 <jgoerzen@complete.org> 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.