Polynomially solvable cases of the bipartite traveling salesman problem

DOI10.1016/J.EJOR.2016.07.060MaRDI QIDQ1752819zbMATH OpenOpenAlexFDO

Authors Alfredo García, 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

bipartite traveling salesmancombinatorial optimizationKalmanson matrixquadrangle propertytraveling salesman

Mathematics Subject Classification ID

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

Recommendations

• An Algorithm for Shortest Paths in Bipartite Digraphs with Concave Weight Matrices and its Applications
• The two-stripe symmetric circulant TSP is in P
• The two-convex-polygons TSP: A solvable case
• Approximation algorithms for the Euclidean bipartite TSP
• scientific article; zbMATH DE number 4027206

Cites work

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

Cited in

(9)

• The two-convex-polygons TSP: A solvable case
• Approximation algorithms for the Euclidean bipartite TSP
• Geometric planar networks on bichromatic collinear points
• scientific article; zbMATH DE number 5819786 (Why is no real title available?)
• Bipartite TSP in o(1.9999ⁿ) time, assuming quadratic time matrix multiplication
• The independent quadratic assignment problem: complexity and polynomially solvable special cases
• Experimental analysis of algorithms for the independent quadratic assignment problem
• The bipartite travelling salesman problem: a pyramidally solvable case
• Retrieval optimization in a warehouse with multiple input/output-points

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

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