Solver for Maximum Colorful Independent Set with Lists ------------------------------------------------------ Build environment: ------------------ * CMake 2.8 * G++ 4.7 tested on Debian GNU/Linux squeeze Build using commands (Linux or Cygwin shell): --------------------------------------------- cmake CMakeLists.txt make How to use: ----------- To solve the problem on a random interval graph with n intervals, maximum compactness m, with at most c colors and a maximum weight w, use ./cis -i i -m m -c c -w w For example ./cis -p -i 10000 -m 100 -c 15 -w 10 The option -p prints the generated interval graph in the program specific format. To solve the problem on an interval graph in a file "graph", use ./cis -f graph Use the option -p to see the maximally compactified interval graph. Interval Graph format: ---------------------- The input format has on each line a right-open interval, which consists of a start point, and end point, a weight, and a list of colors. For example: 1 5 2 1 5 6 9 1 3 6 8 9 10 We have here the interval [1,5) with weight 2 and colors 1, 5, 6, and 9. Moreover, there is an interval [1,3) with weight 6 and colors 8, 9, and 10. René van Bevern