Department of Applied Mathematics & Physics, Kyoto University
Technical Report 2015-004 (October 29, 2015)
Time Bounds on Polynomial-space Exact Algorithms for TSP in Degree-5 and Degree-6 Graphs
by Norhazwani Md Yunos, Aleksandar Shurbevski, Hiroshi Nagamochi
This paper gives a correction to the time bounds on algorithms
for TSP in degree-5 and degree-6 graphs.
A polynomial-space algorithm has been designed
by N. {Md Yunos}, A. Shurbevski and H. Nagamochi for
edge-weighted undirected graphs with maximum degree 5 and degree 6,
respectively in ``A Polynomial-Space Exact Algorithm for TSP in Degree-5
Graphs,'' Technical Reports 2015 [2015-002], Department of Applied
Mathematics and Physics, Kyoto University, 2015 and
``A Polynomial-Space Exact Algorithm for TSP in Degree-6 Graphs,''
Technical Reports 2015 [2015-002], Department of Applied Mathematics and
Physics, Kyoto University, 2015.
These algorithms are branch-and-reduce algorithms that, given a degree-
bounded graph with a set of forced edges,
correctly deliver a minimum cost tour passing through all forced edges,
and
a correct set of branching vectors are derived to determine a best set
of values to vertex weights
in an analysis by the measure-and-conquer method, where one constraint
on vertex weights was mistakenly
unsatisfied with the weights claimed in these reports.
After properly including the constraint,
we have chosen the weight $w($f$i)$ of a degree-$i$ forced vertex (a
vertex to which a forced edge is incident)
and
the weight $w($u$i)$ of a degree-$i$ unforced vertex as:
$w($u5$)=1$,
$w($f5$)=0.491764$,
$w($u4$)=0.700651$,
$w($f4$)=0.347458$,
$w($u3$)=0.322196$ and
$w($f3$)=0.183471$ for degree-5 graphs, which lead to a correct
bound $O^*(2.4723^n)$ on the running time
of the algorithm for an $n$-vertexed degree-5 graph,
and
$w($u6$)=1 $,
$w($f6$)= 0.502801$,
$w($u5$)= 0.815641$,
$w($f5$)= 0.421871$,
$w($u4$)= 0.580698$,
$w($f4$)= 0.311647$,
$w($u3$)=0.262796$, and
$w($f3$)=0.149646$ for degree-6 graphs,
which lead to a correct bound $O^*(3.0335^n)$ on the running time
of the algorithm for an $n$-vertexed degree-6 graph.