	Flat Graph Generator

This generator will generate n-vertex k-partite graphs in which
  (1) Each partition has either ceil(n/k) or floor(n/k) vertices
  (2) The number of edges assigned is very close to the expected
      number of edges given the probability p and partitioning.
  (3) The edges are selected at random from the the pairs in AxB
      subject to the constraints that
      (i)  for any a in A deg(a in AxB) <= ceil(e_{AB} / |B|) + flatness
      (ii) for any b in B deg(b in AxB) <= ceil(e_{AB} / |A|) + flatness

Thus, if flatness is 0, the graph is fairly uniform, while as flatness
increases variance also increases. However, the variance should
always be less than that of an equi-partite graph.

This generator was written after a conversation with Craig Morgenstern
at the DIMACS Challenge workshop. Given the results of the coloring
of graphs with higher variability in the paper with Feng Luo,
and the improvement in hiding made in the graphs Mark Brockington
uses where variance is reduced, we thought similar reductions in 
variance might make the coloring problem more difficult.

This seems to be the case. Although Iterated Greedy, or some combination
of the algorithms I am using still seem to be able to find colorings
of graphs right up to the ridge, the time (e.g. number of iterations)
has increased dramatically over equi-partite graphs in *preliminary* tests.
This seems most apparent for graphs near the ridge.

The generator is in file gen.c

I have placed a few sample graph files. Although the generator
produces output in the DIMACS ASCII format, I have converted them to
the considerably more space efficient binary form using the programs available
from DIMACS. All graphs have edge probability p=0.5 and flatness =0.
There are three of 300 vertices and three of 1000.
In each case there is a graph well to the left of the ridge, one at or near
the ridge boundary and one within the ridge.

I would be interested in hearing of results on these. Also let me know about
any useful modifications to the generator or any problems.

Contact:
	Joseph Culberson
	Department of Computing Science
	University of Alberta
	Edmonton Alberta Canada
	T6G 2H1
	
	joe@cs.ualberta.ca



