|
|
|
|
|
|
 |
|
|
Attacking NP-Hard Graph Problems
|
|
|
|
|
|
| Organization: | Macalester College |
|
|
|
|
|
|
Wolfram Technology Conference 2012
|
|
|
|
|
|
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.
|
|
|
|
|
|
|
|
|
|
|
|
http://www.wolfram.com/events/technology-conference/2012
|
|
|
|
|
|
|
| | | | | |
|
For the newest resources, visit Wolfram Repositories and Archives »
