No subject

[Henry Cejtin]

So,  here  is  a  very  simple  goal  (no algorithm, but I claim this is well
studied by theorists and a simple heuristic must exist):

        You have a directed graph, with  each  node  having  a  size.

        Given  a partition of the nodes, you form a directed graph on
        the partition classes: you have an edge from class A to class
        B  iff  A  and B are distinct and there exists an edge in the
        original graph from some element of A to some element  of  B.

        You wish to find the partition such that

            The  sum of the sizes of the elements of each class is no
                larger than some constant K.

            Given this, you want to minimize the number of edges.

This basically corresponds to saying that we don't know  anything  about  the
edge frequency, but we don't like the edges.

You could use undirected graphs instead.  The argument (a weak one) for using
directed graphs is that it is counting an A->B and a  B->A  edge  separately,
which  is  good  since  if  they both exist, it should increase our desire to
merge A and B.