Cost of sequential connection for points in space

DOI10.1016/0167-6377(89)90039-4MaRDI QIDQ1122502zbMATH OpenOpenAlexFDO

Authors J. Michael Steele

Publication date 1989

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(89)90039-4

zbMATH Keywords

nearest neighbor heuristicsequential minimal insertion procedurespanning treetraveling salseman

Mathematics Subject Classification ID

Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Programming involving graphs or networks (90C35)

Review text

A sequential minimal insertion procedure is used to produce a spanning tree, and the cost is estimated. The technique developed can also be used to the nearest neighbor heuristic for the traveling salseman problem and some other problems.

Recommendations

• On the point-to-point connection problem
• On the connectivity of efficient point sets
• On connectivity spaces
• On connectedness via a sequential method
• scientific article; zbMATH DE number 2245630
• The point-to-point connection problem - analysis and algorithms
• Efficient distance computation in configuration space
• Pathwise Connectivity of the Spatial Numerical Range
• The price of connectivity for feedback vertex set
• The price of connectivity for feedback vertex set

Cites work

• A problem seminar
• An Analysis of Several Heuristics for the Traveling Salesman Problem
• Heuristics Based on Spacefilling Curves for Combinatorial Problems in Euclidean Space
• scientific article; zbMATH DE number 3821646 (Why is no real title available?)
• On the length of optimal TSP circuits in sets of bounded diameter
• Peano curves and smoothness of functions
• Steiner Minimal Trees
• The shortest path and the shortest road through n points

Cited in

(10)

• Quantitative two-scale stabilization on the Poisson space
• Practical distribution-sensitive point location in triangulations
• scientific article; zbMATH DE number 3891093 (Why is no real title available?)
• scientific article; zbMATH DE number 4156450 (Why is no real title available?)
• On the greedy walk problem
• THE NEAREST UNVISITED VERTEX WALK ON RANDOM GRAPHS
• On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\)
• Quantitative CLTs on the Poisson space via Skorohod estimates and p-Poincaré inequalities
• Siblings in d-dimensional nearest neighbour trees
• Finding the root in random nearest neighbor trees

This page was built for publication: Cost of sequential connection for points in space

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