| Paper title: |
Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases |
| DOI: | https://doi.org/10.4316/JACSM.201601006 |
| Published in: | Issue 1, (Vol. 10) / 2016 |
| Publishing date: | 2016-04-14 |
| Pages: | 36-41 |
| Author(s): | MAHARESI Retno |
| Abstract. | Cycle bases belong to a k-connected simple graph used both for listing and enumerating Hamiltonian cycles contained in a planar graph. Planar cycle bases have a weighted induced graph whose weight values limited to 1. Hence making it was possible used in the Hamiltonian cycle enumeration procedures efficiently. In this paper a Hamiltonian cycle enumeration scheme is obtained through two stages. First, i cycles out of m bases cycles are determined using an appropriate constructed constraint. Secondly, to search all Hamiltonian cycles which are formed by the combination of i bases cycles obtained in the first stage efficiently. This efficiency achieved through a generation a class of objects as the representation of i cycle combinations among m bases cycles. The experiment conducted based on the proposed algorithm successfully generated and enumerated all the Hamiltonian cycles contained in a well-known example of planar graph. |
| Keywords: | Enumeration, Hamiltonian Cycle, Planar, Cycle Bases, Connected Graph |
| References: | 1. Eppstein D. “The traveling salesman problem for cubic graphs”, Journal of Graph Algorithms and Applications. 11(1): pp. 61–81, 2007. 2. Michail D. “Minimum cycle Bases: Algorithm & Applications”, Dissertation of Doctor of the Engineering Sciences (Dr.-Ing.) of the natural-technical faculties of, Saarland University, Russia. 2006. 3. Amaldi E., Liberti L., Maculan N., and Maffioli F. “Efficient edge-swapping heuristics for finding minimum fundamental cycle bases”. In WEA 04: 3rd international workshop on experimental and efficient algorithms, Angra dos Reis, Brazil, 2004. 4. Broersma H. J., Fomin F. V., Van’t Hof P. and Paulusma D, “Fast exact algorithms for hamiltonicity in claw-free graphs”. In: 35th International Workshop on Graph-Theoretic Concepts in Computer Science. 591. pp. 44 -53. 2009. 5. Gebauer H. “Finding and enumerating Hamilton cycles in 4-regular graphs” extended abstract appeared in Proc.5th Workshop on Analytic Algorithmics and Combinatorics (ANALCO), 2008. 6. Leydold J. and Stadler P.F.” Minimal Cycle Bases of Outer Planar Graphs”, Preprint Series. Department of Applied Statistics and Data Processing, 1998. 7. Buchin K., Knauer C., Kriegel K., Schulz A., and Seidel R. “On the number of cycles in planar graphs”, In Proceedings of COCOON, pp. 97-107, Springer, 2007. 8. Iwama K.. and Nakashima T. “An Improved Exact Algorithm for Cubic Graph TSP”. Proc. 13th Annual International Computing and Combinatorics Conference (COCOON).pp. 108–117, 2007. 9. Grotschel M. and Lovasz L. “Combinatorial Optimization”. DIMACS Technical Report: 93 (29), 1993. 10. Deo, N., G. Prabhu .M. and Krishnamoorthy M.S. “Algorithms for Generating Fundamental Cycles in a Graph”, ACM Transactions on Mathematical Software: 8(1) : 26-42, 1982. 11. Biswas, S. Durocher, D. Mondal, R. Nishat I. “Hamiltonian Paths and Cycles in Planar Graphs”. COCOA: 83-94, 2012. 12. Kaufman, S. M. “Graph Theory and Linear Algebra” 2004. 13. Vajnowski V. Extended abstract: “Simple Gray codes constructed by ECO method”, 2008. |
| Back to the journal content | |
