Mathematica 9 is now available

Wolfram Library Archive


Courseware Demos MathSource Technical Notes
All Collections Articles Books Conference Proceedings
Title

Attacking NP-Hard Graph Problems
Author

Stan Wagon
Organization: Macalester College
Conference

Wolfram Technology Conference 2012
Conference location

Champaign, Illinois, USA
Description

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.
Subject

*Wolfram Technology
URL

http://wtc12.crowdvine.com/talks/28447
http://www.wolfram.com/events/technology-conference/2012