y.algo
Class IndependentSets

java.lang.Object
  y.algo.IndependentSets

public class IndependentSets
extends Object

This class provides methods for calculating independent sets.

Method Summary

static NodeList	getIndependentSet(Graph conflictGraph) Calculates an independent set for a given conflict graph (each pair of nodes of the independent set is non-adjacent in the conflict graph).
static NodeList[]	getIndependentSets(Graph conflictGraph) Partitions the vertex set of the given conflict graph into independent sets.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

getIndependentSets

public static NodeList[] getIndependentSets(Graph conflictGraph)

Partitions the vertex set of the given conflict graph into independent sets.

Parameters:

conflictGraph - the input graph.

Returns:

a NodeList array where each entry contains an independent set of nodes.

See Also:

getIndependentSet(y.base.Graph)

Precondition:

The input graph is simple, i.e. it contains neither multi-edges nor selfloops.

getIndependentSet

public static NodeList getIndependentSet(Graph conflictGraph)

Calculates an independent set for a given conflict graph (each pair of nodes of the independent set is non-adjacent in the conflict graph). We use a greedy heuristic which tries to find a large independent set.

Parameters:

conflictGraph - the input graph.

Returns:

a NodeList containing an independent set of nodes

Precondition:

The input graph is simple, i.e. it contains neither multi-edges nor selfloops.