Generating all cycles, chordless cycles, and Hamiltonian cycles with the principle of exclusion

An efficient method to generate all edge sets X ⊆ E of a graph G = ( V , E ) , which are vertex-disjoint unions of cycles, is presented. It can be tweaked to generate (i) all cycles, (ii) all cycles of cardinality ⩽5, (iii) all chordless cycles, (iv) all Hamiltonian cycles.

Saved in:
Bibliographic Details
Published in:Journal of discrete algorithms (Amsterdam, Netherlands) Netherlands), 2008-03, Vol.6 (1), p.93-102
Main Author: Wild, Marcel
Format: Article
Language:English
Subjects:
Generating all chordless cycles
Generating all cycles
Generating all Hamiltonian cycles
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An efficient method to generate all edge sets X ⊆ E of a graph G = ( V , E ) , which are vertex-disjoint unions of cycles, is presented. It can be tweaked to generate (i) all cycles, (ii) all cycles of cardinality ⩽5, (iii) all chordless cycles, (iv) all Hamiltonian cycles.
ISSN:1570-8667
1570-8675
DOI:10.1016/j.jda.2007.01.005