pith. sign in

arxiv: 2504.19608 · v5 · submitted 2025-04-28 · 💻 cs.DM · math.CO· math.OC

The frequency K_is for symmetrical traveling salesman problem

Yong Wang This is my paper

Pith reviewed 2026-05-22 19:22 UTC · model grok-4.3

classification 💻 cs.DM math.COmath.OC
keywords symmetric traveling salesman problemoptimal Hamiltonian cycleedge frequencyi-vertex pathsdynamic programmingTSP algorithmaverage-case analysissubgraph frequencies
0
0 comments X

The pith

In symmetric TSP, edges in the optimal Hamiltonian cycle appear with frequency above half the number of optimal i-vertex paths while ordinary edges fall below a much lower threshold.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the frequency K_i of edges across all binomial(i,2) optimal i-vertex paths with fixed endpoints inside each subgraph K_i for i from 4 to n. It shows that any edge belonging to the optimal Hamiltonian cycle exceeds frequency 1/2 binomial(i,2) while non-cycle edges stay below 2(n-3), with the gap widening on average as i grows. Optimal-cycle edges reach their highest frequency near i equal to n/2 plus a small constant, whereas ordinary edges become steadily rarer in the optimal paths once i surpasses a threshold of order n to the 4/7. These frequency rules are turned into a dynamic-programming procedure that recovers the full optimal cycle.

Core claim

For a given K_i the frequency of an optimal-Hamiltonian-cycle edge exceeds 1/2 binomial(i,2) while the frequency of any ordinary edge is less than 2(n-3). In the average case the probability that an optimal-cycle edge appears in the optimal i-paths is non-decreasing with i, and each such edge attains its peak frequency at i = P_0 (n/2 + 2 for even n, (n+1)/2 + 1 for odd n). The inclusion probability of every ordinary edge decreases with i and drops definitively once i reaches i_d = O(n^{4/7}), the smallest integer satisfying the stated ratio inequality. These properties support a dynamic-programming algorithm that finds the optimal Hamiltonian cycle.

What carries the argument

Frequency K_i: the number of times a given edge appears among the binomial(i,2) optimal i-vertex paths with fixed endpoints inside the complete subgraph K_i.

If this is right

  • The dynamic-programming procedure recovers the optimal Hamiltonian cycle in O(n² i_d⁴ 2^{i_d}) time with i_d = O(n^{4/7}).
  • Optimal-cycle edges reach peak frequency at i = P_0 ≈ n/2 + 2.
  • Ordinary-edge inclusion probabilities decrease monotonically with i in the average case.
  • Once i meets or exceeds i_d the decrease for ordinary edges is guaranteed by the given ratio inequality.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same frequency signature might be used to prune search spaces inside branch-and-bound solvers for other cycle problems.
  • If the i_d scaling remains favorable on sparse graphs, the method could be adapted to non-complete TSP instances.
  • Sampling optimal paths only up to size roughly n/2 could yield a practical heuristic that still captures the optimal-cycle edges with high probability.

Load-bearing premise

The set of optimal i-vertex paths with fixed endpoints can be enumerated or estimated accurately enough to compute the frequency thresholds without already knowing the global optimal Hamiltonian cycle.

What would settle it

A symmetric TSP instance in which, for some i, at least one optimal-cycle edge appears in at most half of the optimal i-vertex paths or at least one ordinary edge appears in more than 2(n-3) of them.

Figures

Figures reproduced from arXiv: 2504.19608 by Yong Wang.

Figure 1
Figure 1. Figure 1: The illustration of OHC in Kn. 2. The optimal i-vertex paths and frequency Ki For symmetric T SP, there are n vertices and n 2  edges in Kn (n ≥ 4). If an edge is contained in OHC, it is called an OHC edge. Otherwise, it is an ordinary edge. The T SP containing one OHC is considered here. If some T SP includes several or many OHCs, one can add small random distances to the distances of edges, and convert … view at source ↗
Figure 2
Figure 2. Figure 2: The i 2  OPi s in one Ki. Optimal i-vertex path (OPi ) : Given one Ki on a set of i vertices {v1, v2, . . . , vi−1, vi} in Kn, the paths P i = (vσ1 , . . . , vσi ) visit each of the i vertices exactly once. Fix the two endpoints of P i , such as vσ1 = v1 and vσi = v2, there are (i − 2)! P i s where v1 and v2 are the endpoints. The shortest one is taken as the optimal i-vertex path denoted as OP i for v1 a… view at source ↗
Figure 3
Figure 3. Figure 3: The two G5s contained in the Gi containing all edges in the i 2  OPi s in Ki. in the Gi yet not in the G5. If one vertex of degree 3, such as v2, v3, v4 or v5, does not connected to the other vertices not in the G5 for building the OPi s, the minimum vertex degree of the Gi is 3. Moreover, if v1 is not connected to the other vertices not in the G5 for building the OPi s, v1 maintains the degree 4 in the G… view at source ↗
Figure 4
Figure 4. Figure 4: The changes of pi(g ∈ OPi ) = 1 − h 1 − i+4 i(i−1) i r − 2 i(i−1) and pdi(g) = pi(g ∈ OPi ) − pi+1(g ∈ OPi+1) > 0 according to i ∈ [4, 1000] for n = 1000. to i + 1 ≤ 590 in most cases. In the experiments, pdi(g) > 2pi(g∈OP i ) i(i−1) exists if i ≥ 81. Moreover, pdi(g) > pi(g∈OP i ) i+1 happens from i = 448 to 999. Once pi(g ∈ OPi ) decreases from certain id, it will decrease in proportion to a bigger facto… view at source ↗
Figure 1
Figure 1. Figure 1: In each of the frequency Kis, g is an ordinary edge and it has the frequency f2(g) < i − 3 on average. Because g contains two vertices, g is contained in K = 2n−4 i−4  − n−6 i−6  frequency Kis where f2(g) < i − 3 exists. Since an edge is contained in n−2 i−2  frequency Kis, the K frequency Kis occupy r = 2(i−2)(i−3) (n−2)(n−3)− (i−2)(i−3)(i−4)(i−5) (n−2)(n−3)(n−4)(n−5) of the total frequency Kis contain… view at source ↗
Figure 5
Figure 5. Figure 5: The changes of r and 1 − r according to ϵ ∈ [2 × 10−6 , 1] for n = 1000. well as ϵ ≥ 1 − q 1 2 × r ( i 2)−2i+6 ( i 2)−i+2 . As i is relatively big, ϵ ≥ 1 − q 1 2 = 0.2929 is computed. Because ϵ = (i−2)(i−3) (n−2)(n−3) , i ≥ [ √ ϵ(n − 2.5) + 2.5] = [0.5412n + 1.1470] is derived. Since i begins from 4 rather than zero, i ≥ [0.5412n+ 5.1470] is used. From i = [0.5412n + 5.1470], g has the average frequency f(… view at source ↗
Figure 6
Figure 6. Figure 6: The smallest id meeting the inequality (5) according to n ∈ [1E3, 1E7]. decreases from i = 92 > 80. It means that i 2−4i+7 2 is too small as the average frequency f1(g) if pi(g ∈ OPi ) increases according to i. Thus, the ordinary edges contained in the OP ns have a big average frequency as i is small. Only if i > id, pi(g ∈ OPi ) begins decreasing according to i. Meanwhile, f(g) increases slower than that … view at source ↗
Figure 7
Figure 7. Figure 7: The percents of J, K, L and J + L frequency Kis according to i ∈ [4, 1000] for n = 1000. become smaller according to i in the average case. In each of the K frequency Kis, g has the frequency f2(g) < i+2 2 on average. Except the K frequency Kis containing g, g will not have the maximum frequency f1(g) = i 2  − 1 in each of the other frequency Kis. These frequency Kis include the frequency Kis containing g… view at source ↗
Figure 8
Figure 8. Figure 8: The changes of the ordered probabilities related to all edges according to [PITH_FULL_IMAGE:figures/full_fig_p062_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: The frequency and probability changes for three [PITH_FULL_IMAGE:figures/full_fig_p063_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: The frequency and probability changes for three [PITH_FULL_IMAGE:figures/full_fig_p066_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The frequency and probability changes for three general [PITH_FULL_IMAGE:figures/full_fig_p069_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: The frequency and probability changes for three general [PITH_FULL_IMAGE:figures/full_fig_p070_12.png] view at source ↗
Figure 13
Figure 13. Figure 13: The sparse graphs computed with respect to the probability decrement for the [PITH_FULL_IMAGE:figures/full_fig_p074_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: The sparse graphs computed with respect to the probability decrement for the [PITH_FULL_IMAGE:figures/full_fig_p074_14.png] view at source ↗
Figure 15
Figure 15. Figure 15: The percent changes for the ordinary edges ( [PITH_FULL_IMAGE:figures/full_fig_p088_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: The probability changes for all edges and [PITH_FULL_IMAGE:figures/full_fig_p092_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: The probability changes for all edges and [PITH_FULL_IMAGE:figures/full_fig_p093_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: The probability changes for all edges and [PITH_FULL_IMAGE:figures/full_fig_p093_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: The probability changes for ten OHC edges with the smallest probabilities and ten ordinary edges with the biggest probabilities at i = 4 for rd100. ment is relatively big according to the small number i, and it becomes smaller according to the bigger number i, see the probability change for edge (2,77) in [PITH_FULL_IMAGE:figures/full_fig_p094_19.png] view at source ↗
read the original abstract

The frequency $K_i$s ($i\in[4,n]$) are studied for symmetric traveling salesman problem ($TSP$) to characterize the structure properties of the edges in optimal Hamiltonian cycle ($OHC$). For a given $K_i$ in the complete graph $K_n$, the frequency $K_i$ is computed with the set of ${{i}\choose{2}}$ optimal $i$-vertex paths with fixed endpoints (optimal $i$-vertex paths) in the $K_i$. Given an $OHC$ edge related to $K_i$, it has certain frequency bigger than $\frac{1}{2}{{i}\choose{2}}$ in the frequency $K_i$, and that of an ordinary edge not in $OHC$ is smaller than $2(n-3)$. Moreover, given a frequency $K_i$ containing an $OHC$ edge related to $K_n$, the frequency of the $OHC$ edge is bigger than $\frac{1}{2}{{i}\choose{2}}$ in the average case. It also found that the probability that an $OHC$ edge is contained in the optimal $i$-vertex paths increases according to $i\in [4, n]$ or keeps stable if it decreases from $i$ to $i+1\leq n$. As the frequency $K_i$s are used to compute the frequency of an edge, each $OHC$ edge reaches its own peak frequency at $i=P_0$ where $P_0=\frac{n}{2} + 2$ for even $n$ or $\frac{n+1}{2} + 1$ for odd $n$. For each ordinary edge out of $OHC$, the probability that they are contained in the optimal $i$-vertex paths decreases according to $i$, respectively, in the average case. Moreover, the probability of an ordinary edge definitely decreases if $i \geq i_d$ where $i_d = O(n^{\frac{4}{7}})$ is the smallest number meeting the inequality $\frac{(n-2)(n-3) - (i_d-2)(i_d-3)}{(n-2)(n-3) - (i_d-1)(i_d-2)} \geq \sqrt{1 + \frac{2}{i_d(i_d+1)}}$. Based on these findings, an algorithm is presented to find $OHC$ in $O(n^2i_d^42^{i_d})$ time using dynamic programming. The experiments are executed to verify these findings with various $TSP$ instances.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper defines frequency K_i (for i from 4 to n) in the complete graph K_n for the symmetric TSP as the occurrence counts of edges within the collection of binom(i,2) optimal i-vertex paths with fixed endpoints inside each K_i subgraph. It claims that edges belonging to the optimal Hamiltonian cycle (OHC) exhibit frequency strictly greater than (1/2) binom(i,2) while ordinary edges have frequency less than 2(n-3); these thresholds are asserted to hold in the average case, with OHC-edge inclusion probabilities non-decreasing in i and ordinary-edge probabilities strictly decreasing for i >= i_d = O(n^{4/7}) under a stated inequality. An O(n^2 i_d^4 2^{i_d})-time dynamic-programming algorithm is presented that purportedly exploits these frequencies to recover the OHC, and the claims are said to be verified by experiments on various TSP instances.

Significance. If the frequency thresholds and non-circularity of the underlying optimal-path enumeration can be rigorously established, the work would supply a novel structural characterization of OHC edges together with an explicit subexponential algorithm whose complexity is parameterized by the concrete i_d bound; the explicit DP runtime and the average-case probability statements would constitute falsifiable predictions that could be tested on standard TSP libraries.

major comments (3)
  1. [Abstract] Abstract: the central frequency inequalities (OHC edges > ½ binom(i,2) and ordinary edges < 2(n-3)) are stated without derivation, proof, or error analysis; because the subsequent algorithm and the i_d threshold rest directly on these inequalities, their absence is load-bearing for the correctness claim.
  2. [Abstract] Abstract and algorithm description: the claimed O(n² i_d⁴ 2^{i_d}) runtime presupposes that the set of optimal i-vertex paths for all relevant endpoint pairs can be obtained by a DP whose state space remains inside the stated envelope once the combinatorial factor for choosing the i vertices (or all endpoint pairs) is included; no explicit recurrence or state definition is supplied to confirm this accounting.
  3. [Abstract] Abstract: the i_d = O(n^{4/7}) threshold is derived from the inequality [(n-2)(n-3) - (i_d-2)(i_d-3)] / [(n-2)(n-3) - (i_d-1)(i_d-2)] >= sqrt(1 + 2/(i_d(i_d+1))), yet no proof is given that this inequality forces ordinary-edge inclusion probabilities to decrease uniformly in the average case across the tested instances.
minor comments (2)
  1. Notation for the frequency K_i is introduced without a formal definition or example computation for small i; a concrete small-n illustration would clarify the counting of the binom(i,2) paths.
  2. The experimental section reports verification on “various TSP instances” but supplies neither the instance names, sizes, nor the precise method used to compute the optimal i-vertex paths, preventing independent reproduction.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each major comment point by point below and outline the revisions we will make to improve clarity and rigor.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central frequency inequalities (OHC edges > ½ binom(i,2) and ordinary edges < 2(n-3)) are stated without derivation, proof, or error analysis; because the subsequent algorithm and the i_d threshold rest directly on these inequalities, their absence is load-bearing for the correctness claim.

    Authors: We acknowledge that the abstract states the frequency inequalities concisely without an explicit derivation or error analysis. The body of the manuscript provides supporting reasoning based on the enumeration of optimal i-paths and average-case observations, along with experimental verification. However, we agree that a self-contained derivation is necessary given the load-bearing role of these bounds. We will add a dedicated subsection deriving the OHC-edge lower bound (> ½ binom(i,2)) and ordinary-edge upper bound (< 2(n-3)) from the definition of optimal paths, including a brief discussion of the average-case assumptions and any applicable error bounds. revision: yes

  2. Referee: [Abstract] Abstract and algorithm description: the claimed O(n² i_d⁴ 2^{i_d}) runtime presupposes that the set of optimal i-vertex paths for all relevant endpoint pairs can be obtained by a DP whose state space remains inside the stated envelope once the combinatorial factor for choosing the i vertices (or all endpoint pairs) is included; no explicit recurrence or state definition is supplied to confirm this accounting.

    Authors: The manuscript presents the DP algorithm at a conceptual level to exploit the frequency thresholds. We agree that an explicit recurrence and state-space accounting are required to verify that the combinatorial factors for vertex subsets and endpoint pairs fit inside the O(n² i_d⁴ 2^{i_d}) envelope. We will revise the algorithm section to include the precise DP recurrence, state definition, and a step-by-step complexity analysis that incorporates the binomial factors for choosing the i vertices while remaining within the claimed bound. revision: yes

  3. Referee: [Abstract] Abstract: the i_d = O(n^{4/7}) threshold is derived from the inequality [(n-2)(n-3) - (i_d-2)(i_d-3)] / [(n-2)(n-3) - (i_d-1)(i_d-2)] >= sqrt(1 + 2/(i_d(i_d+1))), yet no proof is given that this inequality forces ordinary-edge inclusion probabilities to decrease uniformly in the average case across the tested instances.

    Authors: The inequality is introduced as the minimal i_d guaranteeing that ordinary-edge inclusion probabilities are strictly decreasing for i ≥ i_d in the average case, based on our analysis of path-inclusion probabilities. We recognize that the manuscript does not supply a complete formal proof that the inequality implies uniform decrease across all instances. We will expand the relevant section with the intermediate steps linking the inequality to the probability monotonicity under the stated average-case model, and we will add a note on the scope of the uniformity claim. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected; derivation is self-contained

full rationale

The paper defines frequency K_i directly from the collection of optimal i-vertex paths (shortest paths on exactly i vertices with fixed endpoints) inside each K_i subgraph. These subproblem optima are independent of the global OHC and can be computed via dynamic programming on subsets of size at most i_d without presupposing the full tour. The claimed frequency thresholds (>½ binom(i,2) for OHC edges, <2(n-3) for ordinary edges) and the average-case probability inequalities (including the explicit inequality used to derive i_d = O(n^{4/7})) are presented as derived properties rather than tautological re-statements of the input definitions. The O(n² i_d⁴ 2^{i_d}) algorithm follows from applying DP to these smaller subproblems and using the resulting frequencies for edge classification; no step reduces the central claim to its own inputs by construction, and no self-citation chain is invoked to justify uniqueness or ansatz choices. The derivation therefore stands as an independent characterization against external subproblem benchmarks.

Axiom & Free-Parameter Ledger

1 free parameters · 2 axioms · 1 invented entities

The central claims rest on the existence of well-defined optimal i-vertex paths for every i and every pair of endpoints, on the validity of average-case probability statements over TSP instances, and on the correctness of the dynamic programming recurrence that uses the frequency thresholds. No independent evidence is supplied for these assumptions beyond the abstract's experimental mention.

free parameters (1)
  • i_d
    The threshold i_d = O(n^{4/7}) is derived from an inequality involving n and i_d; its precise constant factors and the choice of the square-root expression appear fitted to make the probability decrease hold.
axioms (2)
  • domain assumption Optimal i-vertex paths exist and can be identified independently for each i and each pair of fixed endpoints.
    Invoked when defining frequency K_i as the count over the set of binom(i,2) optimal i-vertex paths.
  • ad hoc to paper The average-case probability inequalities for OHC edges versus ordinary edges hold uniformly across the tested TSP instances.
    Used to justify the peak-frequency location P_0 and the monotonic decrease for ordinary edges.
invented entities (1)
  • frequency K_i no independent evidence
    purpose: A new counting measure that aggregates how often an edge appears inside optimal i-vertex paths with fixed endpoints.
    Introduced to characterize OHC edges; no external falsifiable prediction is given beyond the internal frequency thresholds.

pith-pipeline@v0.9.0 · 6021 in / 1924 out tokens · 76596 ms · 2026-05-22T19:22:48.770982+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    P.The traveling salesman problem and its vari- ations

    Gutin, G., and Punnen, A. P.The traveling salesman problem and its vari- ations. Combinatorial Optimization, Springer, Heidelberg, 2007

    work page 2007

  2. [2]

    Karp, R. M. On the computational complexity of combinatorial problems. Networks, 1975, 5(1), 45–68. 97 A C D B 3 5 3 A B D C 5 3 5 A B C D 5 1 5 B A D C 5 1 5 B A C D 5 3 5 C A B D 3 5 3 Figure B.21: The frequency on each edge in the sixOP4s in Figure A.20 (b)

    work page 1975

  3. [3]

    Dynamic programming treatment of the travelling salesman problem.Journal of the ACM (JACM), 1962, 9(1), 61–63

    Bellman, R. Dynamic programming treatment of the travelling salesman problem.Journal of the ACM (JACM), 1962, 9(1), 61–63

    work page 1962

  4. [4]

    Held, M., and Karp, R. M. A dynamic programming approach to sequenc- ing problems.Journal of the Society for Industrial and Applied mathemat- ics, 1962, 10(1), 196–210

    work page 1962

  5. [5]

    Levine, M. S. Finding the right cutting planes for the TSP.Journal of Experimental Algorithmics (JEA), 2000, 5(6), 1–20

    work page 2000

  6. [6]

    L., Bixby, R

    Applegate, D. L., Bixby, R. E., Chvtal, V., Cook, W., Espinoza, D. G., Goycoolea, M., and Helsgaun, K. Certification of an optimal TSP tour through 85,900 cities.Operations Research Letters, 2009, 37(1), 11–15

    work page 2009

  7. [7]

    Exact solution of large-scale, asymmetric traveling salesman problems.ACM Transactions on Mathemat- ical Software (TOMS), 1995, 21(4), 394–409

    Carpaneto, G., Dell’Amico, M., and Toth, P. Exact solution of large-scale, asymmetric traveling salesman problems.ACM Transactions on Mathemat- ical Software (TOMS), 1995, 21(4), 394–409

    work page 1995

  8. [8]

    A comparison of lower bounds for the sym- metriccirculanttravelingsalesmanproblem.Discrete Applied Mathematics, 2011, 159(16), 1815–1826

    De Klerk, E., and Dobre, C. A comparison of lower bounds for the sym- metriccirculanttravelingsalesmanproblem.Discrete Applied Mathematics, 2011, 159(16), 1815–1826

    work page 2011

  9. [9]

    The traveling salesman problem: postcards from the edge of im- possibility (Plenary talk).In The 30th European Conference on Operational Research, Dublin, Ireland, 2019, June

    Cook, W. The traveling salesman problem: postcards from the edge of im- possibility (Plenary talk).In The 30th European Conference on Operational Research, Dublin, Ireland, 2019, June

    work page 2019

  10. [10]

    Liu, Y. H. Diversified local search strategy under scatter search framework for the probabilistic traveling salesman problem.European Journal of Op- erational Research, 2008, 191(2), 332–346

    work page 2008

  11. [11]

    Jonker, R., andVolgenant, T.Nonoptimaledgesforthesymmetrictraveling salesman problem.Operations Research, 1984, 32(4), 837–846

    work page 1984

  12. [12]

    Hougardy, S., and Schroeder, R. T. Edge elimination in TSP instances. Lecture Notes in Computer Science, 2014, 8747, 275–286

    work page 2014

  13. [13]

    https://doi.org/10.48550/arXiv.1809.10469, 2018

    Zhong, X.Smoothed analysis of edge elimination for Euclidean TSP. https://doi.org/10.48550/arXiv.1809.10469, 2018

    work page doi:10.48550/arxiv.1809.10469 2018

  14. [14]

    Lin, S., Kernighan, B. W. An effective heuristic algorithm for the traveling- salesman problem.Oper. Res., 1973, 21, 498–516. 98

    work page 1973

  15. [15]

    An effective implementation of the Lin-Kernighan traveling salesman heuristic.Eur

    Helsgaun, K. An effective implementation of the Lin-Kernighan traveling salesman heuristic.Eur. J. Oper. Res, 2000, 126(1), 106–130

    work page 2000

  16. [16]

    General k-opt submoves for the Lin-Kernighan TSP heuristic

    Helsgaun, K. General k-opt submoves for the Lin-Kernighan TSP heuristic. Math. Program. Comput., 2009 1(2–3), 119–163

    work page 2009

  17. [17]

    A backbone based TSP heuristic for large instances.J

    Jäger, G., Dong, C.X., Goldengorin, B., Molitor, P., and Richter, D. A backbone based TSP heuristic for large instances.J. Heuristics, 2014, 20:107–124, DOI 10.1007/s10732-013-9233-y

    work page doi:10.1007/s10732-013-9233-y 2014

  18. [18]

    An approximate method to compute a sparse graph for traveling salesman problem.Expert Systems with Applications, 2015, 42(12), 5150– 5162

    Wang, Y. An approximate method to compute a sparse graph for traveling salesman problem.Expert Systems with Applications, 2015, 42(12), 5150– 5162

    work page 2015

  19. [19]

    Wang, Y., and Remmel, J. B. A Binomial Distribution Model for the Trav- eling Salesman Problem Based on Frequency Quadrilaterals.Journal of Graph Algorithms and Applications, 2016, 20(2), 411–434

    work page 2016

  20. [20]

    Wang, Y. Sufficient and necessary conditions for an edge in the optimal Hamiltonian cycle based on frequency quadrilaterals.Journal of Optimiza- tion Theory and Applications, 2019, 181(2), 671–683

    work page 2019

  21. [21]

    Finding the edges in optimal Hamiltonian cycles based on fre- quency quadrilaterals.Theoretical Computer Science, 2024, 986, 114323

    Wang, Y. Finding the edges in optimal Hamiltonian cycles based on fre- quency quadrilaterals.Theoretical Computer Science, 2024, 986, 114323

    work page 2024

  22. [22]

    Wang, Y. Application of frequency graph based on group theory in the trav- eling salesman problem.Journal of Zhengzhou University (Natural Science Edition), 2025, 57(1), DOI:10.13705/j.issn.1671–6841.2023186

    work page doi:10.13705/j.issn.1671 2025

  23. [23]

    B., He, Y

    Wang, Y., Liu, P. B., He, Y. L. Frequency bounds for edges and paths in optimal Hamiltonian cycle based on frequencyKis.Experts Systems with Applications, 2025, 278, 127264

    work page 2025

  24. [24]

    http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

    Reinelt, G. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/

    work page

  25. [25]

    Mittelmann, H.D.http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html. 99

    work page