A minimum Hamiltonian completion of a
graph G
is a minimum-size set of edges that, when added
to G, guarantee a Hamiltonian path. Finding a
Hamiltonian completion has applications to
frequency assignment as well as distributed
computing. If the new edges are deleted from the
Hamiltonian path, one is left with a
minimum path cover, a minimum-size set of
vertex-disjoint paths that cover the vertices of
G. For arbitrary graphs, constructing a minimum
Hamiltonian completion or path cover is clearly
NP-hard, but there exists a linear-time
algorithm for trees. In this paper we first give
a description and proof of correctness for this
linear-time algorithm that is simpler and more
intuitive than those given previously. We show
that the algorithm extends also to unicyclic
graphs. We then give a new method for finding an
optimal path cover or Hamiltonian completion for
a tree that uses a reduction to a maximum flow
problem. In addition, we show how to extend the
reduction to construct, if possible, a covering
of the vertices of a bipartite graph with
vertex-disjoint cycles, that is, a 2-factor.
|