The Travelling Salesman Problem and Minimum Matching in the Unit Square
From MaRDI portal
Publication:3967062
DOI10.1137/0212009zbMath0501.68033OpenAlexW2133226747MaRDI QIDQ3967062
Kenneth J. Supowit, Edward M. Reingold, David Alan Plaisted
Publication date: 1983
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0212009
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, Approximation schemes for node-weighted geometric Steiner tree problems, Quantizers ad the worst case Euclidean traveling salesman problem, A concentration inequality for the facility location problem, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, Minimum weight Euclidean \((1+\varepsilon)\)-spanners, The physicist's approach to the travelling salesman problem. II, A randomized \(O(\log^2k)\)-competitive algorithm for metric bipartite matching, Worst-case minimum rectilinear Steiner trees in all dimensions, An upper bound for the average length of the euclidean minimum spanning tree, Lower bounds for rectilinear Steiner trees in bounded space, Heuristic methods and applications: A categorized survey, A partitioning algorithm for minimum weighted Euclidean matching, Partitioning heuristics for two geometric maximization problems
