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 335
- Downloads 0
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...
Identification of Core Architecture Classes for Object-Oriented Software Systems
The new member of the software development team needs to understand the software prior making modifications to the unknown system. The core classes that constitute the system architecture can reveal important structural...
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...
Enhanced White Cane for Visually Impaired People
ccording to WHO (World Health Organization) statistics, around 285 billion people in the world have visual impairment. They find difficulty in doing their everyday tasks and detecting objects in front of them that can be...
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...