On two geometric problems related to the travelling salesman problem
From MaRDI portal
Publication:3343801
DOI10.1016/0196-6774(84)90029-4zbMath0551.90093OpenAlexW2022563199MaRDI QIDQ3343801
Umesh V. Vazirani, Christos H. Papadimitriou
Publication date: 1984
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(84)90029-4
Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Integer programming (90C10)
Related Items
md-MST is NP-hard for, The complexity of Snake and undirected NCL variants, A 4-approximation of the \(\frac{2\pi }{3} \)-MST, The maximum infection time of the \(P_3\) convexity in graphs with bounded maximum degree, Low-degree minimum spanning trees, Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations, What would Edmonds do? Augmenting paths and witnesses for degree-bounded MSTs, On the area requirements of Euclidean minimum spanning trees, On the parameterized complexity of the acyclic matching problem, Improved algorithms in directional wireless sensor networks, Two New Classes of Hamiltonian Graphs, An Integer Programming Model for Branching Cable Layouts in Offshore Wind Farms, On length-sensitive Fréchet similarity, Smoothed analysis of partitioning algorithms for Euclidean functionals, Approximations for node-weighted Steiner tree in unit disk graphs, Unnamed Item, The Parameterized Complexity of Motion Planning for Snake-Like Robots, Priority functions for the approximation of the metric TSP, Not being (super)thin or solid is hard: A study of grid Hamiltonicity, Polynomial area bounds for MST embeddings of trees, A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees, The snowblower problem, Spectrally Robust Graph Isomorphism, The travelling salesman and the PQ-tree, Bounded-angle spanning tree: modeling networks with angular constraints, On improved bounds for bounded degree spanning trees for points in arbitrary dimension, Approximation algorithms for multiple terminal, Hamiltonian path problems, Low-degree minimal spanning trees in normed spaces, Using Lagrangian dual information to generate degree constrained spanning trees, Cooperative TSP, Minimum-weight two-connected spanning networks, DEGREE-CONSTRAINED MINIMUM SPANNING TREE PROBLEM IN STOCHASTIC GRAPH, Algorithms for Euclidean Degree Bounded Spanning Tree Problems, Probabilistic Analysis of the Degree Bounded Minimum Spanning Tree Problem, Degree bounded bottleneck spanning trees in three dimensions, A unifying model for locally constrained spanning tree problems, Walking through waypoints, The complexity of symmetric connectivity in directional wireless sensor networks, The Maximum Time of 2-neighbour Bootstrap Percolation in Grid Graphs and Parametrized Results, Degree-bounded minimum spanning trees, Euclidean bottleneck bounded-degree spanning tree ratios, On exact solutions to the Euclidean bottleneck Steiner tree problem, A push-relabel approximation algorithm for approximating the minimum-degree MST problem and its generalization to matroids, Min-weight double-tree shortcutting for Metric TSP: Bounding the approximation ratio, The vertex degrees of minimum spanning trees, A 4-approximation of the \(\frac{ 2 \pi}{ 3} \)-MST
