Cover
Distinguished Dissertations in Computer Science
Efficient Algorithms for Listing Combinatorial Structures
Copyright
9780521450218
9780521117883
Table of Contents
Abstract
Acknowledgements
Declaration
General References
Index of Notation and Terms
1. Introduction
1.1. Families of Combinatorial Structures
1.2. Motivation
1.2.1. Designing Useful Algorithms
1.2.2. Discovering General Methods for Algorithm Design
1.2.3. Learning about Combinatorial Structures
1.3. Listing Algorithms
1.4. Efficient Listing Algorithms
1.5. Synopsis of the Thesis
1.6. Bibliographic Notes
2. Techniques for Listing Combinatorial Structures
2.1. Basic Building Blocks
2.1.1. Recursive Listing
2.1.2. Random Sampling
2.2. Using Listing Algorithms for Closely Related Families
2.2.1. The Interleaving Method
2.2.2. The Filter Method
2.3. Avoiding Duplicates
2.3.1. Probabilistic Algorithms
Example 1: A family of colorable graphs
Example 2: A family of unlabeled graphs
2.3.2. Deterministic Algorithms
Example 1: A family of colorable graphs
Example 2: A family of unlabeled graphs
3. Applications to Particular Families of Structures
3.1. First Order Graph Properties
3.2. Hamiltonian Graphs
3.3. Graphs with Cliques of Specified Sizes
3.3.1. Graphs with Small Cliques
3.3.2. Graphs with Large Cliques
3.3.3. Graphs with Cliques whose Sizes are Between log(n) and 2 log(n)
3.4. Graphs which can be Colored with a Specified Number of Colors
3.4.1. Digression โ The Problem of Listing k-Colorings
4. Directions for Future Work on Listing
5. Related Results
5.1. Comparing Listing with other Computational Problems
5.2. Evaluating the Cycle Index Polynomial
5.2.1. Evaluating and Counting Equivalence Classes
5.2.2. The Difficulty of Evaluating the Cycle Index Polynomial
5.2.3. The Difficulty of Approximately Evaluating the Cycle Index Polynomial
6. Bibliography