Newsgroups: sci.math
From: hoey@zogwarg.etl.army.mil (Dan Hoey)
Date: 16 Jul 91 19:28:58 GMT
Subject: Re: How about this Travelling Salesman?

dt...@unix.cis.pitt.edu (David M Tate) writes:

>Recognition version:
>Given an arbitrary graph G, does G contain a Hamiltonian cycle?

No, that's Hamiltonian cycle.  The recognition version of TSP is:

Given a graph G with positive integer edge weights and a positive
integer K, does G contain a Hamiltonian cycle of weight at most K?

Dan Hoey
hoey@ETL.Army.Mil