**More efficient algorithms for Hamiltonian Cycles:**
Combinatorica has an implmentation of algorithm to find Hamiltonian
Cycles. However, not too much attention has been paid to making
it efficient. This project involves speeding up the HamitonianQ
algorithm in Combinatorica. The following page might be the place to start.
http://www.ing.unlp.edu.ar/cetad/mos/Hamilton.html

**Hamiltonian cycles and paths in Cayley Graphs:**
The "minimum change" graphs on permutations that we studied
in class are all examples of Cayley Graphs. These graphs have many nice
properties that makes it easier to solve hard problems on them.
We are interested in finding algorithms and heuristics to solving
the Hamiltonian cycle problem quickly in Cayley graphs. The following
article might be a good place to start:
David Witte and Joseph A. Gallian, A survey: Hamiltonian cycles in
Cayley graphs, Discrete Mathematics, 51 (1984) 293-304.

**Graph Isomorphism:**
A fundamental open problem in graph theory is determining whether a given
pair of graphs are isomorphic. No one knows if this problem can be solved
in polynomial time or if it is NP-hard. Combinatorica contains a somewhat
simple implementation of a graph isomorphism algorithm. This project involves
using more sophisticated algorithms to speedup Combinatorica's implementation.
A software called "Nauty" is the best known implementation of graph isomorphism
software. It might be a good idea to start at Nauty's home page at
http://cs.anu.edu.au/~bdm/nauty/

**Multi-permutations:**
Multi-permutations are permutations of multisets. This project involves
enumerating, ranking, unranking, and selecting uniformly at random
multi-permutations.
Knuth's "The Art of Computer Programming, Volume 3" is a place to start
for stuff on permutations of multisets.

**Enumerating Unlabeled Graphs:**
Enumerating labeled graphs is easy, but not unlabeled graphs. There is a
function in Combinatorica called ListGraphs that is extremely slow. This
project involves implementing efficient algorithms for enumerating unlabeled
graphs. The place to start on this project is:
F. Harary, E.M. Palmer, Graphical Enumeration, Academic Press, New York and London, 1973.