Universal conditions for algebraic travelling salesman problems to be efficiently solvable

DOI10.1080/02331939108843720zbMath0732.90088OpenAlexW4244086314MaRDI QIDQ3360022

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)

Related Items (11)

A general approach to avoiding two by two submatrices ⋮ On the traveling salesman problem with a relaxed Monge matrix ⋮ On the recognition of permuted bottleneck Monge matrices ⋮ Efficiently solvable special cases of hard combinatorial optimization problems ⋮ Hamiltonian cycles in circulant digraphs with two stripes ⋮ Perspectives of Monge properties in optimization ⋮ The travelling salesman and the PQ-tree ⋮ GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY ⋮ An \(O(n)\) algorithm to solve the Bottleneck Traveling Salesman Problem restricted to ordered product matrices ⋮ Pyramidal tours for the traveling salesman ⋮ Special cases of the traveling salesman problem

Cites Work

• Extreme Hamiltonian lines
• An equivalency problem in discrete programming over ordered semigroups
• An algebraic approach to assignment problems
• Edgeconvex Circuits and the Traveling Salesman Problem
• A solvable case of the traveling salesman problem
• Unnamed Item
• Unnamed Item

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