Whats the best time complexity, for a known algorithm, that when called generates the next, unique, graph, in order of node count?

For example, the first result being the only single node graph, I request a new graph, it takes 2 units of time as that graph has two nodes, I request the next and it takes 3 units of time giving me 3 nodes in a line. The forth also has 3 nodes, joined in a triangle, so this call still takes just 3 units of time, etc...

This example, that probably has better time complexity than the best available algorithm, takes linear time for the number of nodes in the output graph.

More specifically, to answer TravisJ, To put it another way, an element in the set of all graphs, where no other element has fewer nodes, that has not yet been output by the algorithm.

Put another way, the next graph is a graph with the current number of nodes that has not yet been generated. The number of nodes may need to be increased by one, allowing for a slightly larger graph to be the result.

If this needed to be done with an exhaustive search, I could imagine the time complexity being rather steep, such as exponential or factorial.

  • $\begingroup$ In order to answer this question sufficiently, you need to better describe how your algorithm generates "the next graph." Or at least how "the next graph" is defined. $\endgroup$ – TravisJ Mar 20 '15 at 20:53
  • $\begingroup$ Labeled graphs with $n$ nodes can be indexed by/generated from binary strings of length ${n \choose 2}$ (because there are $2^{n \choose 2}$ labeled graphs with $n$ nodes), but if you only want non-isomorphic graphs, that's a whole different story. $\endgroup$ – pjs36 Mar 20 '15 at 21:27
  • $\begingroup$ Yes, the vanilla non-isomorphic, connected, unlabelled sort. $\endgroup$ – alan2here Mar 20 '15 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.