2

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.

Hans
  • 31
  • 2
  • 3
    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. – Saeed Apr 08 '14 at 12:38
  • 1
    You can search hard instances of problems which can be easily reduced to dominating set. For example search "DIMACS graph benchmarks vertex cover". – Marzio De Biasi Apr 08 '14 at 13:59
  • @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. – Saeed Apr 08 '14 at 14:07
  • @Saeed: I'll wait OP's clarifications :) – Marzio De Biasi Apr 08 '14 at 14:25
  • 4
    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. – Chad Brewbaker Apr 08 '14 at 14:38
  • I'm not sure I got the question correctly, but you might want to check out this link: http://cstheory.stackexchange.com/questions/739/data-for-testing-graph-algorithms – Alex Golovnev Apr 08 '14 at 16:48
  • @Saeed My algorithms are heuristics. I would like to analyze if my heuristics give me results like other algorithms for minimal dominanting set. So I looking for some graphs which already have been tested from other people. – Hans Apr 08 '14 at 18:51
  • @AlexGolovnev I am looking if there exists some graphs from other people who tested domination set on it. – Hans Apr 08 '14 at 18:56
  • @hans I can guess this but is not clear from ur question. So edit it. Also mention that what did u already found and why databases in others comment is not suitable for you. Write them all in your question. – Saeed Apr 08 '14 at 19:13

1 Answers1

3

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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271