Efficient Algorithms for Listing Combinatorial Structures (Distinguished Dissertations in Computer Science)

✍ Scribed by Leslie Ann Goldberg

• Publisher: Cambridge University Press
• Year: 2009
• Tongue: English
• Leaves: 177
• Series: Distinguished Dissertations in Computer Science
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Cover......Page 1
Distinguished Dissertations in Computer Science......Page 3
Efficient Algorithms for Listing Combinatorial Structures......Page 4
9780521117883......Page 5
Table of Contents......Page 6
Abstract......Page 8
Acknowledgements......Page 10
Declaration......Page 11
General References......Page 12
Index of Notation and Terms......Page 13
1.1. Families of Combinatorial Structures......Page 18
1.2.1. Designing Useful Algorithms......Page 21
1.2.3. Learning about Combinatorial Structures......Page 22
1.3. Listing Algorithms......Page 23
1.4. Efficient Listing Algorithms......Page 25
1.5. Synopsis of the Thesis......Page 27
1.6. Bibliographic Notes......Page 30
2.1.1. Recursive Listing......Page 33
2.1.2. Random Sampling......Page 42
2.2. Using Listing Algorithms for Closely Related Families......Page 57
2.2.1. The Interleaving Method......Page 58
2.2.2. The Filter Method......Page 60
2.3.1. Probabilistic Algorithms......Page 64
Example 1: A family of colorable graphs......Page 67
Example 2: A family of unlabeled graphs......Page 69
2.3.2. Deterministic Algorithms......Page 73
Example 1: A family of colorable graphs......Page 77
Example 2: A family of unlabeled graphs......Page 90
3. Applications to Particular Families of Structures......Page 101
3.1. First Order Graph Properties......Page 102
3.2. Hamiltonian Graphs......Page 110
3.3. Graphs with Cliques of Specified Sizes......Page 112
3.3.1. Graphs with Small Cliques......Page 113
3.3.2. Graphs with Large Cliques......Page 115
3.3.3. Graphs with Cliques whose Sizes are Between log(n) and 2 log(n)......Page 120
3.4. Graphs which can be Colored with a Specified Number of Colors......Page 121
3.4.1. Digression — The Problem of Listing k-Colorings......Page 132
4. Directions for Future Work on Listing......Page 136
5.1. Comparing Listing with other Computational Problems......Page 146
5.2. Evaluating the Cycle Index Polynomial......Page 153
5.2.1. Evaluating and Counting Equivalence Classes......Page 157
5.2.2. The Difficulty of Evaluating the Cycle Index Polynomial......Page 159
5.2.3. The Difficulty of Approximately Evaluating the Cycle Index Polynomial......Page 168
6. Bibliography......Page 172