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 356
- Downloads 0
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...
Kalman Filters for Estimating the potential GDP
The estimation of the potential GDP has a twofold importance: on one hand its accurate estimation allows the correct dimensioning of the macroeconomic policies and on the other hand, the study of potential GDP is a resea...
Removal of Baseline Wander Noise from Electrocardiogram (ECG) using Fifth-order Spline Interpolation
Abstract–Baseline wandering can mask some important features of the Electrocardiogram (ECG) signal hence it is desirable to remove this noise for proper analysis and display of the ECG signal. This paper presents the imp...
Dynamic Lyapunov Indicator (DLI): A Perfect indicator for Evolutionary System
Recently proposed indicators along with their abilities for identification of chaotic motion have been described. These are Fast Lyapunov Exponents (FLI), Smaller Alignment Indices (SALI) and Dynamic Lyapunov Indicator (...
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...