Sometimes Travelling is Easy: The Master Tour Problem

DOI10.1137/S0895480195281878MaRDI QIDQ4388980zbMATH OpenOpenAlexFDO

Authors Vladimir G. Deineko, Rüdiger Rudolf, Gerhard J. Woeginger

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 optimizationKalmanson conditionmaster tourpolynomial timetravelling salesman problem

Mathematics Subject Classification ID

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

Recommendations

• Sometimes travelling is easy: The master tour problem
• Three easy special cases of the euclidean travelling salesman problem
• scientific article; zbMATH DE number 34438
• The maximum travelling salesman problem on symmetric Demidenko matrices
• A Note On Kalmanson Matrices^∗

Cited in

(21)

• The multi-stripe travelling salesman problem
• New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
• A priori TSP in the scenario model
• Traveling salesman games with the Monge property
• The trouble with the second quantifier
• On one approach to TSP structural stability
• Four-point conditions for the TSP: the complete complexity classification
• Approximation algorithms for distance constrained vehicle routing problems
• On the complexity of master problems
• A priori TSP in the Scenario Model
• The three-dimensional matching problem in kalmanson matrices
• A Note On Kalmanson Matrices^∗
• Three easy special cases of the euclidean travelling salesman problem
• Packing a knapsack of unknown capacity
• Balancing profits and costs on trees
• The neighbor-net algorithm
• A new tractable case of the QAP with a Robinson matrix
• Sometimes travelling is easy: The master tour problem
• Recognising permuted Demidenko matrices
• Complexity of fixed order routing
• Algorithms for the universal and a priori TSP

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

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