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 (47)
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 ⋮ Spanning closed trail and hamiltonian cycle in grid graphs ⋮ 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
This page was built for publication: On two geometric problems related to the travelling salesman problem
