Four-point conditions for the TSP: the complete complexity classification

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
A solvable case of the quadratic assignment problem
The quadratic assignment problem. Theory and algorithms
The traveling salesman problem and its variations
Another well-solvable case of the QAP: maximizing the job completion time variance
Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
Hamilton Paths in Grid Graphs
A survey of very large-scale neighborhood search techniques
Perspectives of Monge properties in optimization
On the recognition of permuted Supnick and incomplete Monge matrices
The maximum travelling salesman problem on symmetric Demidenko matrices
A New Class of Pyramidally Solvable Symmetric Traveling Salesman Problems
Edgeconvex Circuits and the Traveling Salesman Problem
Extreme Hamiltonian lines
A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
An iterated dynasearch algorithm for the single-machine total weighted tardiness scheduling problem
Monge properties, discrete convexity and applications
Balancing profits and costs on trees
The Steiner tree problem in Kalmanson matrices and in circulant matrices
The three-dimensional matching problem in kalmanson matrices
Sometimes Travelling is Easy: The Master Tour Problem
The maximum traveling salesman problem on van der Veen matrices
Four point conditions and exponential neighborhoods for symmetric TSP
Very large-scale neighborhood search for the quadratic assignment problem
Linear time dynamic-programming algorithms for new classes of restricted TSPs: a computational study
Extended neighborhood: Definition and characterization
On the asymptotic behavior of subtour-patching heuristics in solving the TSP on permuted Monge matrices
On the symmetric traveling salesman problem
Faster strongly polynomial algorithms for the unbalanced transportation problem and assignment problem with Monge costs
Cooperative assignment games with the inverse Monge property
New exponential neighbourhood for polynomially solvable TSPs
On-line sorting of twisted sequences in linear time
A solvable case of the traveling salesman problem
Extreme Hamiltonian Circuits. Resolution of the Convex-Odd Case
Extreme Hamiltonian Circuits. Resolution of the Convex-Even Case
Sparse Monge matrices arising from scheduling problems
One-Sided Monge TSP Is NP-Hard

Cited In (7)

Recognising permuted Demidenko matrices
Polynomial Time Approximation Scheme for Single-Depot Euclidean Capacitated Vehicle Routing Problem
On the Skeleton of the Polytope of Pyramidal Tours
Polynomially solvable cases of the bipartite traveling salesman problem
Two simple but efficient algorithms to recognize Robinson dissimilarities
The multi-stripe travelling salesman problem
Travelling salesman paths on Demidenko matrices

This page was built for publication: Four-point conditions for the TSP: the complete complexity classification

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