GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY

Santosh N. Kabadi ()
Additional contact information
Santosh N. Kabadi: Faculty of Administration, University of New Brunswick, P. O. Box 4400, Fredericton, N.B. E3B 5A3, Canada

International Game Theory Review (IGTR), 2001, vol. 03, issue 02n03, 213-235

Abstract: One of the first and perhaps the most well-known polynomially solvable special case of the traveling salesman problem (TSP) is the Gilmore-Gomory case (G-G TSP). Gilmore and Gomory presented an interesting patching algorithm for this case with a fairly non-trivial proof of its validity. Their work has motivated a great deal of research in the area leading to various generalisations of their results and thereby identification of fairly large polynomially solvable subclasses of the TSP. These results form a major portion of the literature on solvable cases of the TSP. In this paper, we survey the main results on solvable cases of the TSP which are direct generalisations of the G-G TSP and/or the Gilmore-Gomory patching scheme.

JEL-codes: B4 C0 C6 C7 D5 D7 M2 (search for similar items in EconPapers)
Date: 2001
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0219198901000415
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:igtrxx:v:03:y:2001:i:02n03:n:s0219198901000415

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0219198901000415

Access Statistics for this article

International Game Theory Review (IGTR) is currently edited by David W K Yeung

More articles in International Game Theory Review (IGTR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().