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

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...

Coefficient Inequalities for Certain Class of Analytic Functions of Complex Order

In this paper, we define the class b  L of normalized analytic functions of complex order in the open unit disk, sufficient condition involving coefficient inequalities for () fz to be in the class b  L of analytic fun...

Data mining techniques for e-learning

Data Mining (DM), sometimes called Knowledge Discovery in Databases (KDD), is a powerful new technology with great potential to help companies focus on the most important information in the data they have collected via t...

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...

Developing a Mathematical Model to Estimate the Intensity of the Global Radiation

–This research aimed to create an empirical mathematical model to estimate the average monthly of total daily radiation of the global radiation in the middle of northeast Thailand. The model showed the ratio of the month...

Download PDF file
  • EP ID EP444163
  • DOI 10.4316/JACSM.201601006
  • Views 131
  • Downloads 0

How To Cite

MAHARESI Retno (2016). Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases. Journal of Applied Computer Science & Mathematics, 10(21), 36-41. https://europub.co.uk/articles/-A-444163