kamis

Maximum independent sets and vertex covers of large sparse graphs

KaMIS (Karlsruhe Maximum Independent Sets) is an open source project finding maximum independent sets and vertex covers of large sparse graphs. Given a graph G=(V,E), the goal of the maximum independent set problem is to compute a maximum cardinality set of vertices I, such that no vertices in the set are adjacent to one another. Such a set is called a maximum independent set. The problem is NP-hard and particularly difficult to solve in large sparse graphs.