Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases
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 proced...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Stefan cel Mare University of Suceava
2016-04-01
|
| Series: | Journal of Applied Computer Science & Mathematics |
| Subjects: | |
| Online Access: | http://jacsm.ro/view/?pid=21_6 |
| Summary: | 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. |
|---|---|
| ISSN: | 2066-4273 2066-3129 |