Alternative Names: Graph Golf, Order/Degree Problem, Node-Degree-Diameter Problem
The Topology Design problem seeks to construct graphs with optimal communication properties given structural constraints. This problem has applications in network design, where minimizing communication latency (diameter) while limiting connection costs (degree) is crucial.
External Resources:
Given:
- A target number of nodes
$n$ - A maximum degree constraint
$\Delta$
Objective: Find a graph
Diameter: The diameter of a graph is the maximum shortest path distance between any pair of vertices: $$ \text{diam}(G) = \max_{u,v \in V} d(u,v) $$
Note: We do not use average shortest path length as a tiebreaker.
- instances/ - Topology design problem instances
- models/ - Mathematical model formulations
- solutions/ - Optimal or best-known solutions
- check/ - Solution verification tools
- info/ - Additional documentation and papers
- misc/ - Utility scripts and generators
- submissions/ - Community solution submissions
-
Kitasuka, T., Matsuzaki, T., Iida, M. (2018). Order adjustment approach using Cayley graphs for the order/degree problem. IEICE TRANSACTIONS on Information and Systems, 101(12), 2908-2915.
-
Waniek, R. Master's thesis, TU Berlin. Contains extensive references, mathematical models, and useful code (in German).
Both references are available in the info/ directory.