2
$\begingroup$

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.

$\endgroup$
  • 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$ – Hsien-Chih Chang 張顯之 May 17 '11 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 '11 at 13:03
  • 1
    $\begingroup$ Related MO question Database of graphs $\endgroup$ – Pratik Deoghare May 17 '11 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$ – Jukka Suomela May 17 '11 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 '11 at 4:36
8
$\begingroup$

If you want challenging instances for the vertex cover problem:

http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

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

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