Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-25T05:30:48.431Z Has data issue: false hasContentIssue false
  • English
  • Français

Detection of Hamiltonian circuits in a directed graph

Published online by Cambridge University Press:  17 February 2009

Sudhangshu B. Karmakar
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 simple algebraic method is presented to determine the necessary condition for the existence of a Hamiltonian circuit in a directed graph of n vertices. A search procedure is then introduced to identify any or all of the existing Hamiltonian circuits. The procedure is based upon finding a set of edges which will then be candidates for being parts of circuits of length n at any vertex of the graph.

Type
Research Article
Information
The ANZIAM Journal , Volume 24 , Issue 2 , October 1982 , pp. 234 - 242
Copyright
Copyright © Australian Mathematical Society 1982

References

[1]Aho, A. V., Hopcraft, J. E. and Ullman, J. D., The design and analysis of computer algorithms (Addison-Wesley, Reading, Mass., 1974).Google Scholar
[2]Bixby, R. E. and Wang, D., “An algorithm for finding Hamiltonian circuits in certain graphs”, Math. Programming Stud. 8 (1978), 35–49.CrossRefGoogle Scholar
[3]Deo, N., Graph theory with applications to engineering and computer science (Prentice-Hall, Englewood Cliffs, N.J., 1974).Google Scholar
[4]Gary, M. R., Johnson, D. S. and Tarjan, R. E., “The planar Hamiltoman circuit problems is NP complete”, SJAMJ. Comput. 5 (1976), 704–714.Google Scholar
[5]Krishnamoorthy, M. S., “An NP-hard problem in bipartite graphs”, SIGACT News 7 (1975), 1–26.CrossRefGoogle Scholar
[6]Takamizawa, K., Nishizeki, T. and Saito, N., “An O(p3) algorithm for finding Hamiltonian cycles in certain digraphs,” J. Inform. Process. 3 (1980), 68–72.Google Scholar
[7]Yau, S. S., “Generation of all Hamiltonian circuits, paths, and centers of a graph and related problems,” IEEE Trans. Circuit Theory CT–14 (1967), 79–81.CrossRefGoogle Scholar