The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals

DOI10.1007/978-981-19-8152-4_5MaRDI QIDQ6535280zbMATH OpenFDO

Authors Yong Wang

Publication date 2 December 2023

zbMATH Keywords

randomized algorithmtraveling salesman problembounded-degree graphfrequency quadrilateral

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Combinatorial optimization (90C27)

Recommendations

• Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals
• A quick method to compute sparse graphs for traveling salesman problem using random frequency quadrilaterals
• The traveling salesman problem in bounded degree graphs
• The Travelling Salesman Problem in Bounded Degree Graphs
• A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals

Cites work

• A (slightly) improved approximation algorithm for metric TSP
• A Dynamic Programming Approach to Sequencing Problems
• A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights
• A binomial distribution model for the traveling salesman problem based on frequency quadrilaterals
• A branch-and-cut algorithm for the generalized traveling salesman problem with time windows
• A constant-factor approximation algorithm for the asymmetric traveling salesman problem
• A method to compute the sparse graphs for traveling salesman problem based on frequency quadrilaterals
• A near-optimal approximation algorithm for asymmetric TSP on embedded graphs
• A new upper bound for the traveling salesman problem in cubic graphs
• An ETH-Tight Exact Algorithm for Euclidean TSP
• An improved approximation algorithm for ATSP
• Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals
• Certification of an optimal TSP tour through 85,900 cities
• Dynamic Programming Treatment of the Travelling Salesman Problem
• Edge elimination in TSP instances
• Efficient exact algorithms on planar graphs: Exploiting sphere cut decompositions
• Nonoptimal Edges for the Symmetric Traveling Salesman Problem
• On the Computational Complexity of Combinatorial Problems
• POPMUSIC for the travelling salesman problem
• Polylogarithmic approximation for Euler genus on bounded degree graphs
• Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs
• Special frequency quadrilaterals and an application
• Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals
• TSP tours in cubic graphs: beyond 4/3
• The Traveling Salesman Problem for Cubic Graphs
• The frequency of the optimal Hamiltonian cycle computed with frequency quadrilaterals for traveling salesman problem
• The traveling salesman problem and its variations.
• The traveling salesman problem in bounded degree graphs
• The traveling salesman problem on cubic and subcubic graphs
• Tolerance-based branch and bound algorithms for the ATSP

Cited in

(1)

• Bounded degree graphs computed for traveling salesman problem based on frequency quadrilaterals

This page was built for publication: The polynomial randomized algorithm to compute bounded degree graph for TSP based on frequency quadrilaterals

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