Recognition of Gilmore-Gomory traveling salesman problem

DOI10.1016/0166-218X(86)90027-2zbMath0599.90121MaRDI QIDQ1080781

R. Chandrasekaran

Publication date: 1986

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

travelling salesman problempolynomially bounded algorithmGilmore-Gomory algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Numerical mathematical programming methods (65K05)

Related Items (13)

A correction to a result in linear programming ⋮ On the recognition of permuted bottleneck Monge matrices ⋮ Solution algorithms for synchronous flow shop problems with two dominating machines ⋮ An algorithm for the detection and construction of Monge sequences ⋮ Weighted graphs with all Hamiltonian cycles of the same length ⋮ A fast algorithm for constructing Monge sequences in transportation problems with forbidden arcs ⋮ Monge and feasibility sequences in general flow problems ⋮ GENERALISATIONS OF THE GILMORE-GOMORY TRAVELING SALESMAN PROBLEM AND THE GILMORE-GOMORY SCHEME: A SURVEY ⋮ SC-Hamiltonian graphs and digraphs: new necessary conditions and their impacts ⋮ Two machine flow shop scheduling problem with no wait in process: Controllable machine speeds ⋮ Three value TSP and linkages with the three value linear spanning 2-forests ⋮ Special cases of the traveling salesman problem ⋮ Some recent results in the analysis of greedy algorithms for assignment problems

Cites Work

• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem

This page was built for publication: Recognition of Gilmore-Gomory traveling salesman problem