Polynomially solvable cases of the bipartite traveling salesman problem

DOI10.1016/j.ejor.2016.07.060zbMath1394.90480OpenAlexW2477854488MaRDI QIDQ1752819

Alfredo Daniel Garcia, F. Javier Tejel

Publication date: 24 May 2018

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: http://zaguan.unizar.es/record/70658

zbMATH Keywords

combinatorial optimizationtraveling salesmanKalmanson matrixbipartite traveling salesmanquadrangle property

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Combinatorial optimization (90C27)

Related Items (1)

Geometric planar networks on bichromatic collinear points

Cites Work

• Unnamed Item
• Unnamed Item
• On-line sorting of twisted sequences in linear time
• A solvable case of the quadratic assignment problem
• A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem.
• Approximation algorithms for pick-and-place robots
• On Hamiltonian alternating cycles and paths
• Optimal shortest path queries in a simple polygon
• The order of points on the second convex hull of a simple polygon
• The shoelace problem
• The uncapacitated swapping problem on a line and on a circle
• Four-point conditions for the TSP: the complete complexity classification
• The traveling salesman problem and its variations.
• Approximation algorithms for the Euclidean bipartite TSP
• Lacing irregular shoes
• Static pickup and delivery problems: a classification scheme and survey. (With comments and rejoinder)
• The preemptive swapping problem on a tree
• The swapping problem
• Well-Solvable Special Cases of the Traveling Salesman Problem: A Survey
• Approximating Capacitated Routing and Delivery Problems
• The Swapping Problem on a Line
• Approximation algorithms for the capacitated traveling salesman problem with pickups and deliveries
• Edgeconvex Circuits and the Traveling Salesman Problem
• Balancing profits and costs on trees
• The one‐commodity pickup and delivery travelling salesman problem on a path or a tree
• Approximating the Bipartite TSP and Its Biased Generalization

This page was built for publication: Polynomially solvable cases of the bipartite traveling salesman problem