Linear-Time d-Hitting Set Kernelization
---------------------------------------

Build environment:
------------------
 * Boost 1.38
 * CMake 2.8
 * G++ 4.7

tested on Windows 7 using Cygwin, Debian, Fedora.



Build using commands (Linux or Cygwin shell):
---------------------------------------------
 cmake CMakeLists.txt
 make



How to use:
-----------
 The binaries "hslinkern_*" present the various implementations of the
 algorithm as described in the paper "Towards Optimal and Expressive
 Kernelization for d-Hitting Set". That is, with the main data
 structures being the described there "malloc tree", "calloc tree",
 "hash table", and "balanced tree".

 Usage:	./hslinkern_balanced --help



Hypergraph format:
------------------
 The input format has on each line a hyperedge, which consists of
 vertex numbers. An example hypergraph can be generated using

  ./golomb_generator 10

 This generates a GOLOMB SUBRULER conflict graph on 10 vertices. Or,
 alternatively,

  ./random_generator 10 100

 This generates a hypergraph on 10 vertices in which each edge of at
 most four vertices is present with probability 1/100.


      	   René van Bevern <rene.vanbevern@tu-berlin.de>