Combinatorial Generation, Gray Codes, and Structure Problems

组合生成、格雷码和结构问题

• 批准号: 9103431
• 负责人: Carla Savage
• 金额: $ 8.23万
• 依托单位: North Carolina State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1991
• 资助国家: 美国
• 起止时间: 1991-07-01 至 1994-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9103431&HistoricalAwards=false
• 关键词: Combinatorial; Generation; Gray; Codes; Structure

Many practical problems require for their solution the sampling of a random object from a combinatorial class or, worse, an exhaustive search through all objects in the class. In order for such a search to be possible, even for problems of moderate size, combinatorial generation methods must be extremely efficient. As an example, the Gray code approach to combinatorial generation is to generate the objects as a list in which successive elements differ only in a small way, as in the binary reflected Gray code. Each combinatorial Gray code problem has an alternate formulation as a Hamilton path or cycle problem in an associated graph, which may be vertex transitive or even a Cayley graph. Asymptotic improvement in the efficiency of combinatorial generation requires not only good data structures and algorithm design techniques, but, more often, some new insight into the structure of the combinatorial class involved. These structure questions put us into the realm of well-known open problems on Hamilton cycles, graph isomorphism, Cayley graphs, and symmetric chain decompositions in lattices. Progress on the enumeration problems is made by studying the structure problems hand in hand. The research proposed herein is to continue work on combinatorial generation and Gray codes and also to address directly some of the outstanding problems in related areas. These include the Hamilton cycle problem on vertex transitive graphs and Cayley graphs, new problems on de Bruijn - like sequences, and the existence of symmetric chain decompositions and complete matchings in certain partially ordered sets involving permutations and integer partitions.

许多实际问题的解决需要对 随机对象从组合类，或者更糟，一个详尽的 搜索类中的所有对象。 为了进行这样的搜索 即使对于中等规模的问题， 生成方法必须非常有效。 作为一个例子，格雷码方法组合生成 是将对象生成为一个列表，其中连续的元素 不同的只是在一个小的方式，如在二进制反映格雷码。 每个组合格雷码问题都有一个替代公式， 关联图中的汉密尔顿路径或圈问题，这可能是 点传递图甚至是凯莱图 组合算法效率的渐近改进 生成不仅需要良好的数据结构和算法设计 技术，但更多的是，一些新的见解的结构， 涉及的组合类。 这些结构问题让我们 进入领域的著名开放问题的汉密尔顿圈，图 同构，Cayley图和对称链分解 格子 通过对计数问题的研究， 结构性的问题。 本文提出的研究是继续进行组合的工作， 代和格雷码，并直接解决一些 相关领域存在的突出问题。 其中包括汉密尔顿 点传递图和Cayley图的圈问题，新 de Bruijn - like序列的问题，以及对称 链分解和完全匹配 涉及排列和整数划分的有序集。