Enumerating Hamiltonian Cycles in A 2-connected Regular Graph Using Planar Cycle Bases

Maharcsi, Retno (2012) Enumerating Hamiltonian Cycles in A 2-connected Regular Graph Using Planar Cycle Bases. International Workshop on Optimal Network Topologies.

[img]
Preview
Text
Enumerating Hamiltonian Cycles in A 2-connected Regular Graph Using Planar Cycle Bases_UG.pdf - Submitted Version

Download (3113Kb) | Preview

Abstract

Planar fundamental cycle basis belong to a 2-connected simple graph is used for enumerating Hamiltonian cycles contained in the graph. This is because a fun- damental cycle basis is easily constructed. Planar basis is chosen since it has a weighted induced graph whose values are limited to 1. Hence making it is possible to be used in the Hamiltonian cycle enumeration procedures efficiently. In this paper a Hamiltonian cycle enumeration scheme is obtained through two stages. Firstly, i cycles out of m bases cycles are determined using an appropriate con- structed constraint. Secondly, to search all Hamiltonian cycles which are formed by the combination of i basis cycles obtained in the first stage efficiently. This ef- ficiency is achieved through the generation of a class of objects consisting of Ill-bit binary strings which is a representation of i cycle combinations between m cycle basis cycles

Item Type: Article
Uncontrolled Keywords: Cycle bases; Hamiltonian Cycles; enumeration; biconnected graph
Subjects: A General Works > AI Indexes (General)
Divisions: Fakultas Teknologi Industri > Program Studi Teknik Informatika
Depositing User: Mr Reza Chandra
Date Deposited: 25 Feb 2014 08:06
Last Modified: 25 Feb 2014 08:06
URI: http://repository.gunadarma.ac.id/id/eprint/61

Actions (login required)

View Item View Item