Efficient Algorithms for Listing Combinatorial Structures (Distinguished Dissertations in Computer Science, Series Number 5)

✍ Scribed by Leslie Ann Goldberg

• Publisher: Cambridge University Press
• Year: 2009
• Tongue: English
• Leaves: 177
• Edition: 1
• 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
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