Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems

DOI10.1016/0166-218X(91)90044-WzbMath0718.90091OpenAlexW2059097437MaRDI QIDQ2639778

Marek Libura

Publication date: 1991

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(91)90044-w

zbMATH Keywords

lower boundsminimum spanning treeSensitivity analysisedge tolerancesminimum Hamiltonian path

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Sensitivity, stability, parametric optimization (90C31) Computational methods for problems pertaining to operations research and mathematical programming (90-08) Eulerian and Hamiltonian graphs (05C45)

Related Items (17)

Stability of a schedule minimizing mean flow time ⋮ Extending single tolerances to set tolerances ⋮ Global tolerances in the problems of combinatorial optimization with an additive objective function ⋮ Stability analysis in discrete optimization involving generalized addition operations ⋮ Extremal values of global tolerances in combinatorial optimization with an additive objective function ⋮ Efficient computation of tolerances in the weighted independent set problem for some classes of graphs ⋮ On one approach to TSP structural stability ⋮ Sensitivity analysis in the single-machine scheduling problem with max-min criterion ⋮ Tolerance-based branch and bound algorithms for the ATSP ⋮ Reoptimization of the metric deadline TSP ⋮ Reoptimization of the Metric Deadline TSP ⋮ On the Hardness of Reoptimization ⋮ Improving the Efficiency of Helsgaun’s Lin-Kernighan Heuristic for the Symmetric TSP ⋮ Some concepts of stability analysis in combinatorial optimization ⋮ Approximation hardness of deadline-TSP reoptimization ⋮ Stability aspects of the traveling salesman problem based on \(k\)-best solutions ⋮ A note on robustness tolerances for combinatorial optimization problems

Cites Work

• Unnamed Item
• Linear verification for spanning trees
• Maximum of k-th maximal spanning trees of a weighted graph
• Algorithms for updating minimal spanning trees
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• A note on Arc tolerances in sparse shortest-path and network flow problems
• Arc tolerances in shortest path and network flow problems
• Efficiency of a Good But Not Linear Set Union Algorithm
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming

This page was built for publication: Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems