Hostname: page-component-cd9895bd7-dzt6s Total loading time: 0 Render date: 2024-12-23T12:15:23.014Z Has data issue: false hasContentIssue false
  • English
  • Français

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  and
A. Raychaudhuri
D. S. Franzblau
Affiliation:
Department of Mathematics, CUNY, College of Staten Island, 2800 Victory Blvd, Staten Island, NY 10314, USA; e-mail: [email protected].
A. Raychaudhuri
Affiliation:
Department of Mathematics, CUNY, College of Staten Island, 2800 Victory Blvd, Staten Island, NY 10314, USA; e-mail: [email protected].
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.

Type
Research Article
Information
The ANZIAM Journal , Volume 44 , Issue 2 , October 2002 , pp. 193 - 204
Copyright
Copyright © Australian Mathematical Society 2002

References

[1]Boesch, F. T., Chen, S. and McHugh, N. A. M., “On covering the points of a graph with point disjoint paths”, in Graphs and combinatorics (eds. Dold, A. and Eckman, B.), Lecture Notes in Math. 406, (Springer, Berlin, 1974) 201–212.CrossRefGoogle Scholar
[2]Boesch, F. T. and Gimpel, J. F., “Covering the points of a digraph with point-disjoint paths and its application to code optimization”, JACM 24 (1977) 192–198.CrossRefGoogle Scholar
[3]Bondy, J. A. and Murty, U. S. R., Graph theory with applications (North Holland, NY, 1976).CrossRefGoogle Scholar
[4]Diestel, R., Graph theory (Springer, NY, 1997).Google Scholar
[5]Ford, L. R. and Fulkerson, D. R, “A simple algorithm for finding maximal network flows and an application to the Hitchcock problem”, Canadian J. Math. 9 (1957) 210–218.Google Scholar
[6]Goodman, S. E. and Hedetniemi, S. T., “On the Hamiltonian completion problem”, in Graphs and combinatorics (eds. Dold, A. and Eckman, B.), Lecture Notes in Math. 406, (Springer, Berlin, 1974) 262–272.Google Scholar
[7]Goodman, S. E., Hedetniemi, S. T. and Slater, P. J., “Advances on the Hamiltonian completion problem”, JACM. 22 (1975) 352–360.Google Scholar
[8]Hale, W. K., “Frequency assignment: Theory and applications”, roc. IEEE 68 (1980) 1497–1514.Google Scholar
[9]Karejan, Z. A. and Mosesjan, K. M., “The Hamiltonian completion number of a digraph”, Akad. Nauk Armyan. SSR Dokl. 70 (1980) 129–132 (in Russian).Google Scholar
[10]Kornienko, N. M., “The Hamiltonian completion of some classes of graphs”, VestsīAkad. Navuk BSSR, Ser. Fīz.-Mat. Navuk 124 (1982) 18–22 (in Russian).Google Scholar
[11]Kundu, S., “A linear algorithm for the Hamiltonian completion number of a tree”, Info. Proc. Letters 5 (1976) 55–57.CrossRefGoogle Scholar
[12]Lawler, E. L., Combinatorial optimization: Networks and matroids (Holt, Rinehart, and Winston, NY, 1976).Google Scholar
[13]Moran, S. and Wolfstahl, Y., “Optimal covering of cacti by vertex-disjoint paths”, Theoret. Comp. Sci. 84 (1991) 179–197.Google Scholar
[14]Pinter, S. S. and Wolfstahl, Y., “On mapping processes to processors in distributed systems”, Internat. J. Parallel Prog. 16 (1987) 1–15.Google Scholar
[15]Raychaudhuri, A., “Intersection assignments, T-colorings, and powers of graphs”, Ph. D. Thesis, Rutgers Univ., 1985.Google Scholar
[16]Roberts, F. S., Applied combinatorics (Prentice-Hall, Englewood Cliffs, NJ, 1984).Google Scholar
[17]Tucker, A., Applied combinatorics (Wiley, NY, 1980).Google Scholar