Random simple connected graph generation with given sparseness

Question

I'm trying to find an efficient algorithm to generate a simple connected graph with given sparseness. Something like:

Input:
    N - size of generated graph
    S - sparseness (numer of edges actually; from N-1 to N(N-1)/2)
Output:
    simple connected graph G(v,e) with N vertices and S edges

Answer 1

For each node you need at least one vertice.

Start with one node. In each iteration, create a new node and a new vertice. The vertice is to connect the new node with a random node from the previous node set.

After all nodes are created, create random vertices until S is fulfilled. Make sure not to create double vertices (for this you can use an adjancy matrix).

Random graph is done in O(S).

Answer 2

I have the same question as yours Have you do this in matlab?? Would you please send me some matlab code about this to start with?? My email: [email protected]