[comp.misc] Applications for directed hamiltonian circuit finder

ds65+@andrew.cmu.edu (Daniel Stodolsky) (05/06/88)

The problem of determing wether a simple directed graph contains a hamiltonian
cycle is known to be NP-hard. Is there any applications, however, in which one
desired to know wether or not a directed graph is hamiltonian?

I would be indebted to anyone who could mail me a brief description of such
applications. Please do not post responses to this bboard, as I am not a
regular reader.

Thanks in advance,
                Daniel Stodolsky

Daniel Stodolsky
Design Research Center
Carnegie Mellon University

danner@edrc.cmu.edu
ds65@andrew.cmu.edu