Project Suggestions

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.