论文标题
组合灰色代码 - 更新的调查
Combinatorial Gray codes-an updated survey
论文作者
论文摘要
一类对象的组合灰色代码是一个列表，该列表完全包含一个从类中的每个对象，以使列表中的任何两个连续对象仅因“小更改”而有所不同。此类列表以许多不同的组合对象而闻名，包括斑点，组合，排列，分区，三角形，以及针对固定图定义的对象，例如跨越树，完美的匹配或顶点颜色。这项调查提供了有关组合灰色代码研究的最新研究的全面图片。特别是，它提供了有关Savage有影响力的调查的更新[C. D.野蛮人。组合灰色代码的调查。 Siam Rev.，39（4）：605--629，1997。]，结合了许多最新的发展。我们还强调了与图理论，代数，秩序理论，几何学和算法之间紧密相关问题的联系，该问题将该研究领域嵌入更广泛的环境中。最后，我们收集并提出了许多具有挑战性的研究问题，从而刺激了新的研究努力。
A combinatorial Gray code for a class of objects is a listing that contains each object from the class exactly once such that any two consecutive objects in the list differ only by a `small change'. Such listings are known for many different combinatorial objects, including bitstrings, combinations, permutations, partitions, triangulations, but also for objects defined with respect to a fixed graph, such as spanning trees, perfect matchings or vertex colorings. This survey provides a comprehensive picture of the state-of-the-art of the research on combinatorial Gray codes. In particular, it gives an update on Savage's influential survey [C. D. Savage. A survey of combinatorial Gray codes. SIAM Rev., 39(4):605--629, 1997.], incorporating many more recent developments. We also emphasize the connections to closely related problems in graph theory, algebra, order theory, geometry and algorithms, which embeds this research area into a broader context. Lastly, we collect and propose a number of challenging research problems, thus stimulating new research endeavors.
