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

Oscillation Theorems for Fractional Order Neutral Differential Equations

The purpose of this paper is to study the oscillation of the fractional order neutral differential equation 𝑫𝒕 𝜢[𝒓(𝒕)[𝑫𝒕 𝜢(𝒙(𝒕) + 𝒑(𝒕)𝒙(𝝉(𝒕)))]𝜸] + 𝒒(𝒕)π’™πœΈ(𝝈(𝒕)) = 𝟎, where 𝑫𝒕 𝜢(β‹…) is a modified Riemann-Liouville derivati...

Secure and Efficient Diffusion Layers for Block Ciphers

Abstract–Modern block ciphers are designed to meet confusion and diffusion criteria. Substitution and permutation layers are used in the round function for this purpose. In this paper, we present a number of choices for...

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

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

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

Download PDF file
  • EP ID EP444163
  • DOI 10.4316/JACSM.201601006
  • Views 93
  • 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