We provide a corpus of graphs together with their optimal power graph solutions checked into our code repository. Here, for example, is the first graph and its optimal solution for edge-weight 1000, crossing-weight 1. The others are also browsable from there.

These optimal solutions represent hundreds of hours of processing time and should be a valuable resource for both those interested in performing experiments on different representations and algorithms engineers interested in developing more optimal heuristics. For those interested in experimenting with different goal functions or different input graphs our MiniZinc model is also available.

These optimal solutions are useful for experimenting with different goal functions for edge compression and then to test and design more optimal heuristics for finding quick approximate solutions to the problem. Here is our C# implementation of the power-graph heuristic.

Last edited Apr 2, 2013 at 5:06 AM by tgdwyer, version 9

Comments

No comments yet.