Tuesday, December 1, 2015

[DMANET] KaMIS -- Karlsruhe Maximum Independent Sets

Release of KaMIS v1.0

We are pleased to announce the release of our framework KaMIS (Karlsruhe
Maximum Independent Sets). So far our framework contains an advanced
evolutionary algorithm based on graph partitioning (using the KaHIP
partitioning framework) and incorporates kernelization techniques to
compute large independent sets in huge sparse networks. Our algorithm
uses reduction techniques and recursively chooses vertices that are
likely to be in a large independent set, to then further kernelize the
graph. This opens up the reduction space -- which not only speeds up the
computation of large independent sets drastically, but also enables us
to compute high-quality independent sets on massive instances.

The software is released under the GPL 2.0 License.

* open source implementation / website

We are glad for any comments and error reports (or even bug fixes) that
you send us.

Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash and
Renato Werneck
Karlsruhe Institute of Technology (KIT)

* Contributions to be spread via DMANET are submitted to
* DMANET@zpr.uni-koeln.de
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/