Universal conditions for algebraic travelling salesman problems to be efficiently solvable

DOI10.1080/02331939108843720MaRDI QIDQ3360022zbMATH OpenOpenAlexFDO

Authors Rainer E. Burkard, Jack A. A. van der Veen

Publication date 1991

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939108843720

zbMATH Keywords

commutative semigrouptotally orderedtravelling salesman problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Programming in abstract spaces (90C48) Ordered semigroups and monoids (06F05) Semigroups (20M99)

Recommendations

• scientific article; zbMATH DE number 4027206
• scientific article; zbMATH DE number 34438
• An asymmetric analog of van der Veen conditions and the traveling salesman problem. II
• Three easy special cases of the euclidean travelling salesman problem
• scientific article; zbMATH DE number 5819786

Cites work

• scientific article; zbMATH DE number 48301 (Why is no real title available?)
• scientific article; zbMATH DE number 3632217 (Why is no real title available?)
• A solvable case of the traveling salesman problem
• An algebraic approach to assignment problems
• An equivalency problem in discrete programming over ordered semigroups
• Edgeconvex Circuits and the Traveling Salesman Problem
• Extreme Hamiltonian lines

Cited in

(13)

• An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices
• A general approach to avoiding two by two submatrices
• On the recognition of permuted bottleneck Monge matrices
• Efficiently solvable special cases of hard combinatorial optimization problems
• Pyramidal tours for the traveling salesman
• Sometimes travelling is easy: The master tour problem
• The travelling salesman and the PQ-tree
• Generalisations of the Gilmore-Gomory traveling salesman problem and the Gilmore-Gomory scheme: a survey
• Perspectives of Monge properties in optimization
• On the traveling salesman problem with a relaxed Monge matrix
• An asymmetric analog of van der Veen conditions and the traveling salesman problem. II
• Special cases of the traveling salesman problem
• Hamiltonian cycles in circulant digraphs with two stripes

This page was built for publication: Universal conditions for algebraic travelling salesman problems to be efficiently solvable

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