ENUMERATION OF PARTITIONS WITH MINIMUM DIAMETER

We enumerate all the p-partitions of vertices of a complete valued graph (partitions with p classes with minimum diameter DELTA. When p = 2, we recall M.R. Rao's algorithm that permits to count and to enumerate bipartitions. When p > 2, the problem is the same as to build a minimum threshold spanning subgraph G(sigma) having edges greater than DELTA and being p-colourable. So it is an NP-hard problem. First, we use some heuristics to determine sigma, an upper approximation of DELTA, to enumerate all the p colourings of G(sigma). Next we reduce sigma until the partitions remain compatible. When algorithm stops, the diameter of the remaining partitions is the greatest length of an edge lower than the threshold sigma.