HALIN GRAPHS AND THE TRAVELLING SALESMAN PROBLEM
Date
1981-11-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
A Halin graph $H = T cup C$ is obtained by imbedding a tree
$T$ having no degree two nodes in the plane, and then adding a cycle
$C$ to join the leaves of $T$ in such a way that the resulting
graph is planar. These graphs are edge minimal 3-connected, hamiltonian,
and in general have large numbers of hamilton cycles. We show that for
arbitrary real edge costs the travelling salesman problem can be
polynomially solved for such a graph, and we give an explicit
linear description of the travelling salesman polytope (the convex
hull of the incidence vectors of the hamilton cycles) for such
a graph.
Description
Keywords
Computer Science