Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases
Journal Title: Journal of Applied Computer Science & Mathematics - Year 2016, Vol 10, Issue 21
Abstract
sed 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.
Authors and Affiliations
MAHARESI Retno
Keywords
Related Articles
- EP ID EP444163
- DOI 10.4316/JACSM.201601006
- Views 382
- Downloads 0
A Method of Forming the Optimal Set of Disjoint Path in Computer Networks
This work provides a short analysis of algorithms of multipath routing. The modified algorithm of formation of the maximum set of not crossed paths taking into account their metrics is offered. Optimization of paths is c...
Framework for Urdu News Headlines Classification
Automatic text classification has great significance in the field of text mining and plays a pivotal role in areas such as spam filtering, news classification, noise reduction etc. It is evident from the literature that...
Real World Applications of MGR, Neeva and KN-Hash
Hash functions have prominent role in cryptography because of their ubiquitous applications in real world. Earlier, it was used for authentication only but with continuous research and development, it has been started us...
Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases
sed 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...
A Formal Verification Model for Performance Analysis of Reinforcement Learning Algorithms Applied to Dynamic Networks
Routing data packets in a dynamic network is a difficult and important problem in computer networks. As the network is dynamic, it is subject to frequent topology changes and is subject to variable link costs due to cong...