Fast combinatorial and graph algorithms

点击翻译按钮获取中文摘要

Suppose you are given a bag containing blue and yellow beads and are asked the following  questions: How many different necklaces can you make with exactly 5 blue beads and 5 yellow beads?  For this problem observe that the necklace "bbbbbyyyyy"  is the same as "bbyyyyybbb" when the beads are rotated by 3 positions.  Thus, when you attempt to produce a list of such necklaces, it is not a trivial task to ensure that there are no duplicates.This is an example of a problem encounted in the field of "Combinatorial Generation" which is a branch of theoretical computer science.  In this area, the primary research goal is to develop fast computer algorithms to automatically produce exhaustive lists of fundamental mathematical objects - with no duplication.  These objects, such as permutations, combinations, necklaces, and vertex orderings of graphs are often used to model important scientific problems.   As an example, one of the most famous of such algorithms is the Binary Reflected Gray Code.  This algorithm lists all binary numbers of length N so that each successive bit-string differs by exactly one bit from the previous bit-string.   This algorithm was patented and used in pulse code communications.The primary goal of my research is to continue to develop efficient algorithms to produce exhaustive lists for specific objects.  When developing such algorithms, intense study of each object is required, and this often leads to new insights about the object itself.  The algorithms also enhance a toolbox of results that will be crucial for future researchers.