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"

Improve this question
$\endgroup$
6
  • 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, 2010 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, 2010 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, 2010 at 12:16
  • $\begingroup$ I've just found comopt.ifi.uni-heidelberg.de/software/TSPLIB95 anyone have used it? $\endgroup$
    – user770
    Dec 30, 2010 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, 2015 at 16:01

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.