Sometimes Travelling is Easy: The Master Tour Problem

DOI10.1137/S0895480195281878MaRDI QIDQ4388980zbMATHOpenAlexFDO

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

(19)

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

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)