Hostname: page-component-78c5997874-4rdpn Total loading time: 0 Render date: 2024-11-03T08:57:54.971Z Has data issue: false hasContentIssue false
  • English
  • Français

A heuristic method for the determination of a Hamiltonian circuit in a graph

Published online by Cambridge University Press:  17 February 2009

Sudhangshu B. Karmakar
Sudhangshu B. Karmakar
Affiliation:
Bell Communications Research, Piscataway, NJ 08854, USA.
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 heuristic methodology for the identification of a circuit passing through all the vertices only once in a graph is presented. The procedure is based upon defining a normal form of a matrix and then transforming the adjacency matrix into its normal form. For a class of graphs known to be Hamiltonian, it is conjectured that this methodology will identify circuits in a small number of steps and in many cases merely by observation.

Type
Research Article
Information
The ANZIAM Journal , Volume 28 , Issue 3 , January 1987 , pp. 328 - 339
Copyright
Copyright © Australian Mathematical Society 1987

References

[1]Aho, A. V., Hopcroft, J. E., and Ullman, J. D., The design and analysis of computer algorithms (Addison- Wesley, 1974).Google Scholar
[2]Bollobas, B., Graph Theory (Springer-Verlag, 1979).CrossRefGoogle Scholar
[3]Gary, M. R., Johnson, D. S. and Tarjan, R. E., “The planar Hamiltonian circuit problem is NP complete”, SIAM J. Comput. 5 (1976), 704–714.CrossRefGoogle Scholar
[4]Groner, R., Groner, H. and Bischof, W. F., Methods of Heuristics (Lawrence Erlbaum Asso. 1983).Google Scholar
[5]Harary, F., Graph Theory (Addison-Wesley, 1972).Google Scholar
[6]Karmakar, S. B., “Detection of Hamiltonian circuits in a directed graph”, J. Austral. Math. Soc. Ser. B 24 (1982), 234–242.CrossRefGoogle Scholar
[7]Krishnamoorthy, M. S., “An NP hard problem in bipartite graphs”, SIGACT New 7 (1975), 1–2C.Google Scholar
[8]Lesniak-Foster, L., “Some recent results in Hamiltonian graphs”, J. Graph Theory 1 (1977), 27–36.CrossRefGoogle Scholar
[9]Ore, O., “Arc coverings of graphs”, Ann. Mat. Pura Appl. 55 (1961), 315–322.CrossRefGoogle Scholar
[10]Posa, L., “Hamiltonian circuits in random graphs”, Discrete Math. 14 (1976), 359–364.CrossRefGoogle Scholar
[11]Takamizawa, K., Niskizehi, T. and Saito, N., “An 0(p 3) algorithm for finding Hamiltonian cycles in certain digraphs”, J. Inform. Process, 3 (1980), 68–72.Google Scholar