Guaranteed performance heuristics for the bottleneck traveling salesman problem

DOI10.1016/0167-6377(84)90077-4MaRDI QIDQ786658zbMATH OpenOpenAlexWikidataFDO

Authors R. G. Parker, Ronald L. Rardin

Publication date 1984

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(84)90077-4

zbMATH Keywords

biconnected graphsbottleneck traveling salesman problemcomputational complexityconstant-performance, polynomial- time, nonexact algorithmsheuristicminimax traveling salesman problemworst-case behavior

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Analysis of algorithms and problem complexity (68Q25) Integer programming (90C10) Programming involving graphs or networks (90C35)

Cites work

• On spanning subgraphs of a connected bridgeless graph and their application to DT-graphs
• P-Complete Approximation Problems
• The Bottleneck Traveling Salesman Problem
• The square of every two-connected graph is Hamiltonian
• The traveling salesman problem: An update of research

Cited in

(26)

• Best possible heuristics for the bottleneck wandering salesperson and bottleneck vehicle routing problem
• Solving the Euclidean bottleneck biconnected edge subgraph problem by 2- relative neighborhood graphs
• Traveling salesman problem under categorization
• A fast and simple algorithm for the bottleneck biconnected spanning subgraph problem
• Minmax regret solutions for minimax optimization problems with uncertainty
• Establishing symmetric connectivity in directional wireless sensor networks equipped with 2/3 antennas
• Heuristic methods and applications: A categorized survey
• A linear time algorithm for the bottleneck biconnected spanning subgraph problem
• Euclidean bottleneck bounded-degree spanning tree ratios
• An efficient heuristic algorithm for the bottleneck traveling salesman problem
• The complexity of symmetric connectivity in directional wireless sensor networks
• Connectivity and stretch factor trade-offs in wireless sensor networks with directional antennae
• A linear time algorithm for the bottleneck traveling salesman problem on a Halin graph
• Performance guarantees for the TSP with a parameterized triangle inequality
• STRONG CONNECTIVITY IN SENSOR NETWORKS WITH GIVEN NUMBER OF DIRECTIONAL ANTENNAE OF BOUNDED ANGLE
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• The bottleneck 2-connected k-Steiner network problem for k 2
• Experimental analysis of heuristics for the bottleneck traveling salesman problem
• Algorithms for Euclidean degree bounded spanning tree problems
• Symmetric Connectivity in Wireless Sensor Networks with π/3 Directional Antennas
• Traveling salesman problem with clustering
• A survey on approximability of traveling salesman problems using the TSP-T3CO definition scheme
• Optimization of decentralized multi-way join queries over pipelined filtering services
• Ordered median traveling salesman problem
• Strong connectivity of sensor networks with double antennae
• An exact algorithm for the bottleneck 2-connected k-Steiner network problem in L_p planes

This page was built for publication: Guaranteed performance heuristics for the bottleneck traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q786658)