The term colouring is a little confusing (is this a problem you wrote
yourself?). I suppose you mean: find a minimum cardinality set S such
that for each vertex v, either v is in S or at least one of v's
neighbours is in S. This problem is not equivalent to the maximum
independent set problem. It
Colorwave? This seems a rather obscure algorithm for maximum
independent set (that is, if it is actually an algorithm for the max
independent set). Also, minimum dominating set and maximum independent
set are not the same problem (they are not equivalent problems). You
might want to be a little mo
Have you tried google?
For (1), delete that particular edge and test whether the resulting
graph is connected (i.e., do a depth-first search). This solution is
optimal if you want to check whether removing a particular edge
disconnects the graph. In the slightly more general case in which you
wan
Hey,
I have a couple questions concerning graph theory.
1) If I have a connected graph G(V,E), how can I determine if the
removal of a particular graph edge leaves the remaining graph still
"connected"? I mean specifically, how do you test for this in a fast
way?
2) Is there any robust free-wa
