I am looking for a description of the linear time algorithm for the TSP in Halin graphs, that was given in

"G. Cornuejols, D. Naddef, and W.R. Pulleyblank. Halin graphs and the travelling salesman problem. Mathematical Programming, 26:287–294, 1983."

Unfortunately that article isn't freely accessible online and if would a great help for me, if anyone could provide a (link to a) description of that algorithm.

I need that algorithm for checking a new TSP heuristic, that would be based on Halin graphs.

  • 1
    $\begingroup$ I have yet to read the reference, but Halin graphs have bounded treewidth, and TSP can be solvable in linear time on such graphs. $\endgroup$ – S. Pek May 25 '18 at 8:40
  • $\begingroup$ Since you have mentioned that you do not have access to the paper, feel free to email me if you still need it. (My email should be relatively easy to find - my website is linked in my profile.) $\endgroup$ – Martin Sleziak Apr 23 '19 at 8:39

Here is what I could piece together from what is available online and some ruminations of my own:

The edgeset $E$ of a Halin graph $H(V,E),\ deg(v\in V)\ \ge 3,$ can be decomposed into two disjoint sets $T$ and $C$, where $T\cup V$ constitutes to a spanning tree of $H$ and $C\cup \lbrace v\in adj(C)\rbrace$ is a simple cycle through all and only the leafnodes of the spanning tree.

Among the interesting properties of Halin graphs are:

  • because $adj(C)\subset V$ equals the set of leafnodes of $T\cup V$, there is a functional dependency $\phi: V \supset adj(C) \ni c\ \mapsto\ t\in V\setminus adj(C) $, which maps leafnodes to their parent nodes

  • defining a fan as a maximal set of leafnodes with equal parent node, that is adjacent to the edges of a continuous path in $C$, it is possible to disconnect a fan by removing exactly three edges, namely the two on the cycle, that are adjacent to only one fan-vertex and the one connecting the common parent to its grandparent.

  • there are only three possible ways, in which a tour can enter and leave a fan via the three cutedges and one can modify the weight of the cutedges in a way that makes it possible to calculate the overall tour length without descending into the fan; that is made explicit by "shrinking" the fan to a single vertex and assigning to the cutedges a weight that guarantees that the sum of each pair yields the length of the shortest Hamilton path through the vertices adjacent to the respective pair of cutedges plus the fan-edges.

  • shrinking a fan either results again in a smaller Halin graph or in a wheel graph, in which the optimal tour can be easily calculated by optimally inserting the center vertex, which equals the common parent of the cycle vertices, into the sequence of cycle vertices.

the following pictures illustrate what is done:
Three possible tours through a fan
the three possible paths through a fan in a Halin graph; the weightsum of each path is distributed to two cutedges, depicted as solid thick lines.

The colored thick lines correspond to path edges, of which arrows are cycle-edges and undirected lines are tree edges.

Dashed lines are the fan edges that will be contracted; the colored ones are on the optimal path which in turn depends on the pair of given cutedges.

enter image description here
illustration of the distribution of pathlengths to pairs of cutedges.

the modified weight of the cutedges is calculated by solving the system of linear equations

It is also possible to shrink distinct pairs of fans simultaneously, whenever they are not connected via a single edge on the cycle.

| cite | improve this answer | |
  • $\begingroup$ Here is a method you can use to get access to papers like this. I make no comments about the legality. If you go to sci-hub.tw and then paste in the DOI of the paper (including the https), it will give you the pdf. It appears that the paper you seek is 8 pages and is hosted there. $\endgroup$ – David White Apr 23 '19 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.