Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases

Enumerating Hamiltonian Cycles in a Planar Graph Using Combinatorial Cycle Bases

Journal

Subject and more

  • LCC Subject Category:
  • Publisher's keywords: enumeration, Hamiltonian cycle, planar, cycle bases, connected graph
  • Language of fulltext: english
  • Full-text formats available: PDF
  • Time From Submission to Publication:

AUTHORS

    MAHARESI Retno

FULL TEXT

To download PDF files Login to your Account.

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.

About Europub

EuroPub is a comprehensive, multipurpose database covering scholarly literature, with indexed records from active, authoritative journals, and indexes articles from journals all over the world. The result is an exhaustive database that assists research in every field. Easy access to a vast database at one place, reduces searching and data reviewing time considerably and helps authors in preparing new articles to a great extent. EuroPub aims at increasing the visibility of open access scholarly journals, thereby promoting their increased usage and impact.