Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases
| Autor: | Retno MAHARESI |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: | |
| Zdroj: | Journal of Applied Computer Science & Mathematics, Vol 10, Iss 1, Pp 36-41 (2016) |
| Druh dokumentu: | article |
| ISSN: | 20160100 2066-4273 2066-3129 |
| DOI: | 10.4316/JACSM.201601006 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|