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 :
- Misleading Hard Graphs (M-Graphs)1
- Structured Hard Graphs (SHRD)2
- Random Hard Graphs (R)3
- Coordinate Graphs (CRD)4
- 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"