Fast combinatorial and graph algorithms

假设给你一个装有蓝色和黄色珠子的袋子，并问你以下问题：用5颗蓝色珠子和5颗黄色珠子你能做出多少种不同的项链？对于这个问题，观察到当珠子旋转3个位置时，项链“bbbbbyyyyy”与“bbyyyyybbb”相同。因此，当您试图生成这样的项链列表时，确保没有重复可不是一件简单的任务。这是在“组合生成”领域遇到的一个问题的例子，“组合生成”是理论计算机科学的一个分支。在这个领域，主要的研究目标是开发快速的计算机算法来自动生成基本数学对象的详尽列表-没有重复。这些对象，如排列、组合、项链和图的顶点排序，经常被用来为重要的科学问题建模。例如，其中最著名的算法之一是二进制反射灰度码。该算法列出长度为N的所有二进制数，以便每个连续的位串与前一个位串相差1位。该算法已获得专利，并应用于脉冲码通信。我研究的主要目标是继续开发有效的算法，为特定对象生成详尽的列表。在开发这种算法时，需要对每个对象进行深入研究，这通常会导致对对象本身的新见解。这些算法还增强了对未来研究人员至关重要的结果工具箱。

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.