Abstract:
The rapid growth in fields of computational biology, data mining and combinatorial
chemistry results in an increased demand of combinatorial algorithms which produce
exhaustive lists of combinatorial objects especially those objects which are symmetric
under some equivalence relation. In this thesis we develop efficient algorithms for
generation of bracelets with fixed density, bracelets with fixed content, and non-
isomorphic unicyclic graphs. All of the above mentioned algorithms list only one
representative object from each equivalence class.
A bracelet is said to be of fixed density, if number of occurrences of the symbol 0
is fixed. The algorithm for generation of bracelets with fixed density generates a
complete set of bracelets with fixed density of arbitrary base in lexicographic order.
A simple mapping technique is used to prove that our algorithm works in constant
amortized time.
Bracelets with fixed content are those in which number of occurrences of each symbol
is fixed. We devise an efficient algorithm to list bracelets with fixed content in reverse
lexicographic order. Again, by using an injective mapping we prove that the algorithm
works in constant amortized time with the condition that number of occurrences of
the largest symbol is maximum. Our analysis also gives a simpler alternate proof
for the original bracelet algorithm presented in “Generating bracelets in constant
amortized time” by J. Sawada. Moreover, an enumeration formula for bracelets with
fixed content is obtained.
Listing of non-isomorphic graphs is known to be computationally very hard. However,
when we restrict the graphs to have exactly one cycle, the problem can be efficiently
solved in constant amortized time. In this thesis, we give a CAT algorithm to list all
unlabeled non-isomorphic unicyclic graphs.
