0
$\begingroup$

I keep finding references to $G$-Set graphs and I cannot find a definition anywhere.

They are usually mentioned at the same time as the random graph generator "rudy," so I believe they refer to a method of generating graphs but I cannot find out any more than that.

I apologise in advance if I have missed something obvious.

Improve this question
$\endgroup$
1
  • $\begingroup$ It's not obvious to me, if that makes you feel any better. $\endgroup$
    – David White
    Mar 10, 2015 at 17:31

1 Answer 1

Reset to default
1
$\begingroup$

I believe these are the 57 graphs labelled $G_1$ to $G_{57}$ in Table 7 of a preprint by Helmberg and Rendl (http://opus4.kobv.de/opus4-zib/files/306/SC-97-37.pdf). As you thought, they were generated by rudy, and the table lists the data needed to get them from that program.

Apparently, these graphs are accepted as standard test cases for some kinds of problems. In particular, a paper by S.J.Benson, Y.Ye, and X.Zhang http://dx.doi.org/10.1137/S1052623497328008 says: "Our experiments used a machine-independent graph generator, called rudy, created by G.Rinaldi. We tested the maximum cut semidefinite program on the G set of graphs used by Helmberg and Rendl [12]. This set of problems becomes a standard test set for graph optimization."

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Dave this is consistent with everything I've seen, very helpful. $\endgroup$
    – Howard Dale
    Mar 11, 2015 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.