Traveling salesman cycles are not always subgraphs of Voronoi duals

DOI10.1016/0020-0190(83)90004-2MaRDI QIDQ1055435zbMATH OpenOpenAlexFDO

Authors Vitit Kantabutra

Publication date 1983

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(83)90004-2

zbMATH Keywords

Euclidean traveling salesman cycleVoronoi diagram

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45)

Cites work

• Graph theory
• Two-Dimensional Voronoi Diagrams in the L _p -Metric

Cited in

(10)

• Traveling salesman cycles are not always subgraphs of Delaunay triangulations or of minimum weight triangulations
• A non-Hamiltonian, nondegenerate Delaunay triangulation
• An upper bound on the shortness exponent of inscribable polytopes
• Hamiltonian triangulations and circumscribing polygons of disjoint line segments
• Testing the necklace condition for shortest tours and optimal factors in the plane
• Finding Hamiltonian cycles in Delaunay triangulations is NP-complete
• Novel concave hull-based heuristic algorithm for TSP
• 2-change for k-connected networks
• A simple method for resolving degeneracies in Delaunay triangulations
• Toughness and Delaunay triangulations

This page was built for publication: Traveling salesman cycles are not always subgraphs of Voronoi duals

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