Guaranteed performance heuristics for the bottleneck traveling salesman problem

DOI10.1016/0167-6377(84)90077-4zbMath0528.90084OpenAlexW2140787410WikidataQ56019910 ScholiaQ56019910MaRDI QIDQ786658

Ronald L. Rardin, R. Gary Parker

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

computational complexityheuristicbottleneck traveling salesman problemworst-case behaviorbiconnected graphsconstant-performance, polynomial- time, nonexact algorithmsminimax traveling salesman problem

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

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