Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-16T11:45:43.095Z Has data issue: false hasContentIssue false

Optimal Hamiltonian completions and path covers for trees, and a reduction to maximum flow

Published online by Cambridge University Press:  17 February 2009

D. S. Franzblau
Affiliation:
Department of Mathematics, CUNY, College of Staten Island, 2800 Victory Blvd, Staten Island, NY 10314, USA; e-mail: franzblau@postbox.csi.cuny.edu.
A. Raychaudhuri
Affiliation:
Department of Mathematics, CUNY, College of Staten Island, 2800 Victory Blvd, Staten Island, NY 10314, USA; e-mail: raychaudhuri@postbox.csi.cuny.edu.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 2002