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