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 optimizationpolynomial timetravelling salesman problemmaster tourKalmanson condition

Mathematics Subject Classification ID

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

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

(20)

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

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)