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.