Fast combinatorial and graph algorithms

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

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.