I am looking for websites or articles where can I find a data with test graphs for domination set problem. In my heuristic algorithms I use undirected and unweighted graphs. So I search for some graphs which already have been tested from other people.

  • 3
    $\begingroup$ I cannot see any research level statement in the question, but on the other hand when I saw a question I did a google search to see if deserves to downvote, but I didn't find any reference as requested (in quick search), so I think while the question is not well explained, it's also not very welcome to downvote a new user without any explanation. $\endgroup$
    – Saeed
    Apr 8 '14 at 12:38
  • 1
    $\begingroup$ You can search hard instances of problems which can be easily reduced to dominating set. For example search "DIMACS graph benchmarks vertex cover". $\endgroup$ Apr 8 '14 at 13:59
  • $\begingroup$ @MarzioDeBiasi, That's a good idea, then may be is not bad to explain it in more details as answer (e.g by mentioning that it's approximation or heuristic preserving reduction), e.g I personally had no idea about the good search term for the case that OP looking for, but your suggestion seems to be nice. Well, as I said question is not well explained and we don't know what is the OP's algorithm (approximation, heuristic, exact), but your suggestion is nice anyway. $\endgroup$
    – Saeed
    Apr 8 '14 at 14:07
  • $\begingroup$ @Saeed: I'll wait OP's clarifications :) $\endgroup$ Apr 8 '14 at 14:25
  • 4
    $\begingroup$ This is a serious research question. Many query complexity problems can be formulated as DOM sets. I had to roll my own C code for MinDomSet. Any recommendation would be appreciated. $\endgroup$ Apr 8 '14 at 14:38

A quick google search revealed Experiments on Data Reduction for Optimal Domination in Networks. If you look at their tables they cite a number of data sets for which the actual dominating set is given. They also use a number of random graph generators and publish the average dominating set size for these.

There's another paper from 2002: Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem. I couldn't find an online copy, but I'm sure this paper also documents data sets and actual DS sizes.


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.