I have a problem where I need to find the smallest k-coloring for a graph that represents conflicts between objects. Is there a Haskell library that will do this for me? I'm not particularly concerned about speed, and it's unlikely that I'll generate really bad edge cases, but I'd prefer to do something other than write the really bad try-every-case algorithm. -- Alec Story Cornell University Biological Sciences, Computer Science 2012
This may help: - use hMatrix to find the eigenvalues of the adjacency matrix Then by the following theorems: "An upper bound on the chromatic number in terms of eigenvalues was discovered by Wilf(1967). Chromatic Number(G) <= 1 + lambda_1(G) Hoffman (1977) discovered a lower bound on the chromatic number in terms of the smallest and largest eigenvalue. Chromatic Number(G) >= 1 - (lambda_1/lambda_n) for n>=2."
From "The Mutually Beneficial Relationship of Graphs and Matrices", Richard A. Brualdi,CBMS Series,Number 115, 2011.
On Fri, Jul 13, 2012 at 1:43 PM, Alec Story
I have a problem where I need to find the smallest k-coloring for a graph that represents conflicts between objects. Is there a Haskell library that will do this for me? I'm not particularly concerned about speed, and it's unlikely that I'll generate really bad edge cases, but I'd prefer to do something other than write the really bad try-every-case algorithm.
-- Alec Story Cornell University Biological Sciences, Computer Science 2012
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- -- Regards, KC
participants (2)
-
Alec Story -
KC