Re: List of hard Problems with Transitions from underconstrained to overconstrained



Hi,

did you try the following book? :

M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to
the Theory of NP-Completeness. W.H. Freeman and Company, 1979.

Good luck with your research,
OZGUN



Heiko Hamann wrote:
Hi everyone.

I'm searching for a list or any kind of a summary of problems that show
phase transitions in terms of the following:

"Specifically, for large problems, a few parameters characterizing their
structure determine the relative difficulty for a wide variety of common
search methods, on average. Moreover, changes in these parameters give
rise to transitions, becoming more abrupt for larger problems, that are
analogous to phase transitions in physical systems. In this case, the
transition is from underconstrained to overconstrained problems, with
the hardest cases concentrated in the transition region. One powerful
result of this work is that this concentration of hard cases occurs at
the same parameter values for a wide range of search methods. That is,
this behavior is a property of the problems rather than of the details
of the search algorithm."
(Source:
http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume4/hogg96a-html/node3.html)

I'm familiar with this field in general, but I would like to get an
overview of researched problems especially in the group of NP-complete
graph and geometric problems. A list with the names of the problems,
short descriptions, their worst case complexities and descriptions of
the parameters describing their phase transitions would be the _ideal_
thing I'm looking for. But anything else, which could help me here,
would be appreciated.

Thank you for any hint in advance,

Heiko

.