2
$\begingroup$

Degree Constrained Minimum Spanning Tree is an NP-hard problem. It differs from Minimum Spanning Tree in that, degree of every vertex should be $\leq$ some degree constrained. This is a well studied problem. I'm trying to recreate experimentation results described in several papers. In addition to check their algorithms against Random graphs, these papers also use modified instances of random graphs to fool known algorithms.

My question is, Where can I find data sets for the following types of graphs :

  1. Misleading Hard Graphs (M-Graphs)1
  2. Structured Hard Graphs (SHRD)2
  3. Random Hard Graphs (R)3
  4. Coordinate Graphs (CRD)4
  5. Symmetric Graphs (SYM)5

Alternatively, is there any package/tools that can generate them?

1. Knowles and Corne, "A New Evolutionary Approach to the Degree Constrained Minimum Spanning Tree Problem"

2. Krishnamoorthy, "Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree"

3. Boldon-Deo-Kumar, "Minimum Weight Degree Constrained Spanning Tree Problem"

4. Volgenant, "A Lagragian Approach to the Degree Constrained Minimum Spanning Tree Problem"

5. Krishnamoorthy, "Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree"

$\endgroup$
  • 1
    $\begingroup$ this is terribly cryptic. (a) I have no idea what these graphs are, and (b) please specify if "degree constrained MST" is indeed what you're looking for, and what the formal problem defn is ? Not everyone here is familiar with the problem. $\endgroup$ – Suresh Venkat Dec 14 '10 at 10:51
  • $\begingroup$ I just realized referring to papers won't clarify it either. Any clue? Probably, the question is too localized? $\endgroup$ – user770 Dec 14 '10 at 11:09
  • $\begingroup$ It does seem rather specific: we have entertained data set requests here before, but I don't know if this will be deemed as too limited. $\endgroup$ – Suresh Venkat Dec 14 '10 at 12:16
  • $\begingroup$ I've just found comopt.ifi.uni-heidelberg.de/software/TSPLIB95 anyone have used it? $\endgroup$ – user770 Dec 30 '10 at 5:50
  • 1
    $\begingroup$ Maybe this link helps you: cs.hbg.psu.edu/~bui/data/bui-zrncic-gecco2006.html $\endgroup$ – Pooria Kaviani Feb 15 '15 at 16:01

Your Answer

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