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 377
- Downloads 0
Two-dimensional Spectral Approximation
In this article, we propose a two-dimensional polynomial basis which extends Legendre series approximation to bivariate functions. We also present a theoretical study of the stability and the error estimation of the Ta...
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...
IT&C used by Individuals and Economic Development in Romania - Application of Cointegration and Vector Error Correction Model
Since the first decade of the 21st century, information and communication technology has become both a tool for the individual and, in many cases, a way of life. Undoubtedly, the Internet has revolutionized the society i...
Development of Student Information Management System based on Cloud Computing Platform
The management and provision of information about the educational process is an essential part of effective management of the educational process in the institutes of higher education. In this paper the requirements of a...
The Evolution of the Processing Power Needed by the Primary Cryptocurrencies and its profit.
This paper intends to follow the evolution of the processing power needed to mine cryptocurrencies. Because by this year, 2018, they evolved to being over 1500 cryptos, we shell consider reviewing the first 5: Bitcoin, E...