Efficient algorithms for listing combinatorial structures
Efficient algorithms for listing combinatorial structures
复制标题
列出组合结构的高效算法
DOI：
10.1017/cbo9780511569913
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
L. A. Goldberg
中科院分区：
文献类型：
--
作者：
L. A. Goldberg
本论文涉及用于列出组合结构的有效算法的设计。此处描述的研究给出了以下问题的一些答案：哪些组合结构的家族具有快速的计算机算法来列出其成员，哪些一般方法可用于列出组合结构，如何将这些方法应用于理论上感兴趣的家族计算机科学家和组合主义者？在考虑的家族中，有未标记的图，一阶一阶特性，哈密顿图，指定顺序的图形以及可kolor的图。还包括一些相关的工作，将清单问题与解决存在问题，施工问题，随机抽样问题和计数问题的难度进行比较。特别是，评估Polya循环多项式的困难。
This thesis is concerned with the design of efficient algorithms for listing combinatorial structures. The research described here gives some answers to the following questions: which families of combinatorial structures have fast computer algorithms for listing their members, What general methods are useful for listing combinatorial structures, How can these be applied to those families that are of interest to theoretical computer scientists and combinatorialists? Among those families considered are unlabeled graphs, first-order one properties, Hamiltonian graphs, graphs with cliques of specified order, and k-colorable graphs. Some related work is also included that compares the listing problem with the difficulty of solving the existence problem, the construction problem, the random sampling problem, and the counting problem. In particular, the difficulty of evaluating Polya's cycle polynomial is demonstrated.