Sometimes Travelling is Easy: The Master Tour Problem

DOI10.1137/S0895480195281878zbMath0914.90253OpenAlexW2119735681MaRDI QIDQ4388980

Vladimir G. Deǐneko, Gerhard J. Woeginger, Rüdiger Rudolf

Publication date: 11 May 1998

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0895480195281878

zbMATH Keywords

combinatorial optimizationtravelling salesman problempolynomial timemaster tourKalmanson condition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Paths and cycles (05C38) Parallel algorithms in computer science (68W10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (17)

Packing a Knapsack of Unknown Capacity ⋮ Approximation algorithms for distance constrained vehicle routing problems ⋮ The three-dimensional matching problem in kalmanson matrices ⋮ Balancing profits and costs on trees ⋮ On the Complexity of Master Problems ⋮ The multi-stripe travelling salesman problem ⋮ A priori TSP in the Scenario Model ⋮ A Note On Kalmanson Matrices^∗ ⋮ Algorithms for the universal and a priori TSP ⋮ On one approach to TSP structural stability ⋮ New special cases of the quadratic assignment problem with diagonally structured coefficient matrices ⋮ A New Tractable Case of the QAP with a Robinson Matrix ⋮ The neighbor-net algorithm ⋮ A priori TSP in the scenario model ⋮ The trouble with the second quantifier ⋮ Traveling salesman games with the Monge property ⋮ Four-point conditions for the TSP: the complete complexity classification

This page was built for publication: Sometimes Travelling is Easy: The Master Tour Problem