<p>A quick google search revealed <a href="http://theinf1.informatik.uni-jena.de/publications/domset-reduction-annor05.pdf" rel="nofollow">Experiments on Data Reduction for Optimal Domination in Networks</a>. 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. </p>

<p>There's another paper from 2002: <a href="http://link.springer.com/article/10.1007/s00453-001-0101-z" rel="nofollow">Experimental Analysis of Heuristic Algorithms for the Dominating Set Problem</a>. I couldn't find an online copy, but I'm sure this paper also documents data sets and actual DS sizes. </p>

CC BY-SA 3.0
2014-04-09T05:02:19.510Z
2014-04-09T05:02:19.510Z
Suresh Venkat
<p>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.</p>

CC BY-SA 3.0
2014-04-08T12:38:51.927Z
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
CC BY-SA 3.0
2014-04-08T13:59:05.327Z
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
CC BY-SA 3.0
2014-04-08T14:07:30.417Z
@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
CC BY-SA 3.0
2014-04-08T14:25:12.687Z
@Saeed: I'll wait OP's clarifications :)
Marzio De Biasi
CC BY-SA 3.0
2014-04-08T14:38:41.717Z
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
CC BY-SA 3.0
2014-04-08T16:48:55.363Z
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
CC BY-SA 3.0
2014-04-08T18:51:07.003Z
@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
CC BY-SA 3.0
2014-04-08T18:56:16.143Z
@AlexGolovnev I am looking if there exists some graphs from other people who tested domination set on it.
Hans
CC BY-SA 3.0
2014-04-08T19:13:38.677Z
@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
<graph-theory>
Dominating set problem
Hans
# Dominating set problem

(Asked by: username_0 on 2014-04-08)

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.

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.  
> **username_2**: You can search hard instances of problems which can be easily reduced to dominating set. For example search "DIMACS graph benchmarks vertex cover".  
> **username_1**: @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.  
> **username_2**: @username_1: I'll wait OP's clarifications :)  
> **username_3**: 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.  
> **username_4**: 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  
> **username_0**: @username_1 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.  
> **username_0**: @AlexGolovnev I am looking if there exists some graphs from other people who tested domination set on it.  
> **username_1**: @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.  

---

## 1 answers

### Answer by username_5 on 2014-04-09. Score: 3

A quick google search revealed [Experiments on Data Reduction for Optimal Domination in Networks](http://theinf1.informatik.uni-jena.de/publications/domset-reduction-annor05.pdf). 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](http://link.springer.com/article/10.1007/s00453-001-0101-z). I couldn't find an online copy, but I'm sure this paper also documents data sets and actual DS sizes.


---

