Possible Duplicate:
Data for testing graph algorithms

I recently developed a parallel algorithm to solve the vertex cover problem.
now i need some graphs so i can test the speed of my algorithm vs the sequential code.
where can i find graphs? i am looking for something similar to this text file:

3 3
1 0
1 2
0 2

the first 2 numbers (3 and 3) states that there are 3 vertices and 3 edges in the graph. following this line is 3 edges.

  • 1
    $\begingroup$ Hi @scatman: I'm not so sure that your question is within scope, so you may want to try other SE sites as well. $\endgroup$ May 17, 2011 at 11:15
  • $\begingroup$ Check out the answers for the related questions cstheory.stackexchange.com/questions/3409/… cstheory.stackexchange.com/questions/739/… $\endgroup$
    – Snowie
    May 17, 2011 at 13:03
  • 1
    $\begingroup$ Related MO question Database of graphs $\endgroup$ May 17, 2011 at 13:42
  • 1
    $\begingroup$ (The other question specifically asks for directed graphs, but I think it would be a good idea to slightly edit the question to make it more general, and then merge the answers. Also, it might be a good idea to CW the question.) $\endgroup$ May 17, 2011 at 16:47
  • 1
    $\begingroup$ Hi scatman, please read the FAQ. Specifying the format of the input is making your question too localized IMO, so I would suggest that edit that part. Also take a look at the question linked above by Jukka to see if the answers for that question would also answer your question (in which case I can merge the questions so all of the answers are in one place). Thanks. $\endgroup$
    – Kaveh
    May 18, 2011 at 4:36

3 Answers 3


If you want challenging instances for the vertex cover problem:



You can check out the graphs at NetWiki. Of course, you'll have to sort out the formatting yourself.


Here's a collection of graphs that we used for analyzing a vertex cover heuristic: http://www.ru.is/kennarar/eyjo/vertexcover.html

You can download a zipfile containing all the graphs here: http://www.ru.is/kennarar/eyjo/vertexcover/graphs.zip

The format is not exactly as you specified but it's close enough.


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.