# Data set for Degree Constrained MST?

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 :

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"

• 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. Dec 14, 2010 at 10:51
• I just realized referring to papers won't clarify it either. Any clue? Probably, the question is too localized?
– user770
Dec 14, 2010 at 11:09
• 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. Dec 14, 2010 at 12:16
• I've just found comopt.ifi.uni-heidelberg.de/software/TSPLIB95 anyone have used it?
– user770
Dec 30, 2010 at 5:50
• Maybe this link helps you: cs.hbg.psu.edu/~bui/data/bui-zrncic-gecco2006.html Feb 15, 2015 at 16:01