  We give a column generation based branch and bound algorithm for coalition
structure generation over graphs problem using valuation functions for which
this problem is proven to be NP-complete. For a given graph G = (V;E) and a
valuation function w : 2^V -> R, the problem is to find the most valuable
coalition structure (or partition) of V. We consider two cases: first when the
value of a coalition is the sum of the weights of its edges which can be
positive or negative, second when the value of a coalition takes account of
both inter- and intra-coalitional disagreements and agreements, respectively.
For both valuations we give experimental results which cover for the first time
sets of more than forty agents.
  For another valuation function (coordination) we give only the theoretical
considerations in the appendix.
