Wolfram Library Archive

Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings

Attacking NP-Hard Graph Problems

Stan Wagon
Organization: Macalester College

Wolfram Technology Conference 2012
Conference location

Champaign, Illinois, USA

Although many problems about graphs are NP-complete, one can use several of Mathematica's fast algorithms to derive new methods that compute graph parameters with some success. Starting with the very fast blossom algorithm for a maximum matching and calling on integer linear-programming and other methods, I have designed algorithms to compute the following parameters or properties of a graph G: 1. The vertex chromatic number of G. 2. The edge chromatic number of G (found for all 6975 graphs in GraphData, including the Suzuki graph, which has 370656 edges). 3. Finding a Hamiltonian decomposition of G if it exists. 4. Determining Hamilton-connectedness or, in the bipartite case, Hamilton-laceability of G. 5. Finding a perfect 1-factorization of G: an edge coloring such that any two colors combine to form a Hamiltonian cycle. Such computations lead to new conjectures and often point the way to proofs of new theorems.

*Wolfram Technology