Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey

The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the...

Full description

Saved in:
Bibliographic Details
Published in:SIAM review 1998-09, Vol.40 (3), p.496-546
Main Authors: Burkard, Rainer E., Deῐneko, Vladimir G., van Dal, René, Jack A. A. van der Veen, Woeginger, Gerhard J.
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph theory
Heuristics
Itinerant sales
Mathematical models
Mathematical programming
Mathematics
Matrices
Operational research and scientific management
Operational research. Management science
Polynomials
Rectangles
Sciences and techniques of general use
Theoretical computing
Traveling salesman problem
Vanes
Vertices
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3
cites cdi_FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3
container_end_page 546
container_issue 3
container_start_page 496
container_title SIAM review
container_volume 40
creator Burkard, Rainer E.
Deῐneko, Vladimir G.
van Dal, René
Jack A. A. van der Veen
Woeginger, Gerhard J.
description The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-143].
doi_str_mv 10.1137/S0036144596297514
format article
fullrecord <record><control><sourceid>jstor_proqu</sourceid><recordid>TN_cdi_proquest_journals_194202839</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>2653230</jstor_id><sourcerecordid>2653230</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3</originalsourceid><addsrcrecordid>eNplkNFLwzAQxoMoOKd_gOBDEF-rl6RNG9_G0CkICp34WLL2oh1ZM5NusP_elA198Ok4vt99d_cRcsngljGR35UAQrI0zZTkKs9YekRGDFSW5BzgmIwGORn0U3IWwhJiXwg1IrMPtDYpnd3qhUVarrFutaVTHTBQZ2j_hXTu9RZt233SUlsMK93RN-8ivrqnE1pu_BZ35-TEaBvw4lDH5P3xYT59Sl5eZ8_TyUtSCyn6pIjHAkrNURZGZDLnRgNvJBiDKt4veNNgAzo1PMWFaOQg8QIzaUAxZsSYXO991959bzD01dJtfBdXVkylHHj8KkJsD9XeheDRVGvfrrTfVQyqIa7qX1xx5uZgrEOtrfG6q9vwN1gAj2jErvbYMvTO_8pcZoILED_OnHEs</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>194202839</pqid></control><display><type>article</type><title>Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey</title><source>EBSCOhost Business Source Ultimate</source><source>SIAM Journals Archive</source><source>JSTOR Archival Journals and Primary Sources Collection</source><creator>Burkard, Rainer E. ; Deῐneko, Vladimir G. ; van Dal, René ; Jack A. A. van der Veen ; Woeginger, Gerhard J.</creator><creatorcontrib>Burkard, Rainer E. ; Deῐneko, Vladimir G. ; van Dal, René ; Jack A. A. van der Veen ; Woeginger, Gerhard J.</creatorcontrib><description>The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-143].</description><identifier>ISSN: 0036-1445</identifier><identifier>EISSN: 1095-7200</identifier><identifier>DOI: 10.1137/S0036144596297514</identifier><identifier>CODEN: SIREAD</identifier><language>eng</language><publisher>Philadelphia, PA: Society for Industrial and Applied Mathematics</publisher><subject>Algorithmics. Computability. Computer arithmetics ; Algorithms ; Applied sciences ; Combinatorics ; Combinatorics. Ordered structures ; Computer science; control theory; systems ; Exact sciences and technology ; Graph theory ; Heuristics ; Itinerant sales ; Mathematical models ; Mathematical programming ; Mathematics ; Matrices ; Operational research and scientific management ; Operational research. Management science ; Polynomials ; Rectangles ; Sciences and techniques of general use ; Theoretical computing ; Traveling salesman problem ; Vanes ; Vertices</subject><ispartof>SIAM review, 1998-09, Vol.40 (3), p.496-546</ispartof><rights>Copyright 1998 Society for Industrial and Applied Mathematics</rights><rights>1999 INIST-CNRS</rights><rights>Copyright Society for Industrial and Applied Mathematics Sep 1998</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3</citedby><cites>FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.jstor.org/stable/pdf/2653230$$EPDF$$P50$$Gjstor$$H</linktopdf><linktohtml>$$Uhttps://www.jstor.org/stable/2653230$$EHTML$$P50$$Gjstor$$H</linktohtml><link.rule.ids>314,780,784,3185,27924,27925,58238,58471</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=1802629$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Burkard, Rainer E.</creatorcontrib><creatorcontrib>Deῐneko, Vladimir G.</creatorcontrib><creatorcontrib>van Dal, René</creatorcontrib><creatorcontrib>Jack A. A. van der Veen</creatorcontrib><creatorcontrib>Woeginger, Gerhard J.</creatorcontrib><title>Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey</title><title>SIAM review</title><description>The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-143].</description><subject>Algorithmics. Computability. Computer arithmetics</subject><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Combinatorics</subject><subject>Combinatorics. Ordered structures</subject><subject>Computer science; control theory; systems</subject><subject>Exact sciences and technology</subject><subject>Graph theory</subject><subject>Heuristics</subject><subject>Itinerant sales</subject><subject>Mathematical models</subject><subject>Mathematical programming</subject><subject>Mathematics</subject><subject>Matrices</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>Polynomials</subject><subject>Rectangles</subject><subject>Sciences and techniques of general use</subject><subject>Theoretical computing</subject><subject>Traveling salesman problem</subject><subject>Vanes</subject><subject>Vertices</subject><issn>0036-1445</issn><issn>1095-7200</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1998</creationdate><recordtype>article</recordtype><recordid>eNplkNFLwzAQxoMoOKd_gOBDEF-rl6RNG9_G0CkICp34WLL2oh1ZM5NusP_elA198Ok4vt99d_cRcsngljGR35UAQrI0zZTkKs9YekRGDFSW5BzgmIwGORn0U3IWwhJiXwg1IrMPtDYpnd3qhUVarrFutaVTHTBQZ2j_hXTu9RZt233SUlsMK93RN-8ivrqnE1pu_BZ35-TEaBvw4lDH5P3xYT59Sl5eZ8_TyUtSCyn6pIjHAkrNURZGZDLnRgNvJBiDKt4veNNgAzo1PMWFaOQg8QIzaUAxZsSYXO991959bzD01dJtfBdXVkylHHj8KkJsD9XeheDRVGvfrrTfVQyqIa7qX1xx5uZgrEOtrfG6q9vwN1gAj2jErvbYMvTO_8pcZoILED_OnHEs</recordid><startdate>19980901</startdate><enddate>19980901</enddate><creator>Burkard, Rainer E.</creator><creator>Deῐneko, Vladimir G.</creator><creator>van Dal, René</creator><creator>Jack A. A. van der Veen</creator><creator>Woeginger, Gerhard J.</creator><general>Society for Industrial and Applied Mathematics</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>JQ2</scope><scope>U9A</scope></search><sort><creationdate>19980901</creationdate><title>Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey</title><author>Burkard, Rainer E. ; Deῐneko, Vladimir G. ; van Dal, René ; Jack A. A. van der Veen ; Woeginger, Gerhard J.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1998</creationdate><topic>Algorithmics. Computability. Computer arithmetics</topic><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Combinatorics</topic><topic>Combinatorics. Ordered structures</topic><topic>Computer science; control theory; systems</topic><topic>Exact sciences and technology</topic><topic>Graph theory</topic><topic>Heuristics</topic><topic>Itinerant sales</topic><topic>Mathematical models</topic><topic>Mathematical programming</topic><topic>Mathematics</topic><topic>Matrices</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>Polynomials</topic><topic>Rectangles</topic><topic>Sciences and techniques of general use</topic><topic>Theoretical computing</topic><topic>Traveling salesman problem</topic><topic>Vanes</topic><topic>Vertices</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Burkard, Rainer E.</creatorcontrib><creatorcontrib>Deῐneko, Vladimir G.</creatorcontrib><creatorcontrib>van Dal, René</creatorcontrib><creatorcontrib>Jack A. A. van der Veen</creatorcontrib><creatorcontrib>Woeginger, Gerhard J.</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>ProQuest Computer Science Collection</collection><jtitle>SIAM review</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Burkard, Rainer E.</au><au>Deῐneko, Vladimir G.</au><au>van Dal, René</au><au>Jack A. A. van der Veen</au><au>Woeginger, Gerhard J.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey</atitle><jtitle>SIAM review</jtitle><date>1998-09-01</date><risdate>1998</risdate><volume>40</volume><issue>3</issue><spage>496</spage><epage>546</epage><pages>496-546</pages><issn>0036-1445</issn><eissn>1095-7200</eissn><coden>SIREAD</coden><abstract>The traveling salesman problem (TSP) belongs to the most basic, most important, and most investigated problems in combinatorial optimization. Although it is an NP-hard problem, many of its special cases can be solved efficiently in polynomial time. We survey these special cases with emphasis on the results that have been obtained during the decade 1985-1995. This survey complements an earlier survey from 1985 compiled by Gilmore, Lawler, and Shmoys [The Traveling Salesman Problem-A Guided Tour of Combinatorial Optimization, Wiley, Chichester, pp. 87-143].</abstract><cop>Philadelphia, PA</cop><pub>Society for Industrial and Applied Mathematics</pub><doi>10.1137/S0036144596297514</doi><tpages>51</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0036-1445
ispartof SIAM review, 1998-09, Vol.40 (3), p.496-546
issn 0036-1445
1095-7200
language eng
recordid cdi_proquest_journals_194202839
source EBSCOhost Business Source Ultimate; SIAM Journals Archive; JSTOR Archival Journals and Primary Sources Collection
subjects Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Combinatorics
Combinatorics. Ordered structures
Computer science
control theory
systems
Exact sciences and technology
Graph theory
Heuristics
Itinerant sales
Mathematical models
Mathematical programming
Mathematics
Matrices
Operational research and scientific management
Operational research. Management science
Polynomials
Rectangles
Sciences and techniques of general use
Theoretical computing
Traveling salesman problem
Vanes
Vertices
title Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T06%3A15%3A05IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_proqu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Well-Solvable%20Special%20Cases%20of%20the%20Traveling%20Salesman%20Problem:%20A%20Survey&rft.jtitle=SIAM%20review&rft.au=Burkard,%20Rainer%20E.&rft.date=1998-09-01&rft.volume=40&rft.issue=3&rft.spage=496&rft.epage=546&rft.pages=496-546&rft.issn=0036-1445&rft.eissn=1095-7200&rft.coden=SIREAD&rft_id=info:doi/10.1137/S0036144596297514&rft_dat=%3Cjstor_proqu%3E2653230%3C/jstor_proqu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-81130e6a2e68f35672fa02d60ffe961432dded0a4f24eb3d6d60f28e56f0911f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=194202839&rft_id=info:pmid/&rft_jstor_id=2653230&rfr_iscdi=true