grph.algo.covering_packing

Class FominGrandoniKratschMaximumindependentSetAlgorithm

java.lang.Object

grph.GrphAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

grph.algo.covering_packing.FominGrandoniKratschMaximumindependentSetAlgorithm

All Implemented Interfaces:

java.io.Serializable

public class FominGrandoniKratschMaximumindependentSetAlgorithm
extends GrphAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

This class provides an implementation of the algorithm proposed by Fomin, Grandoni and Kratsch for computing a maximum independent set, based on foldable vertices and mirroring, in F.V. Fomin, F. Grandoni, and D. Kratsch, A measure & conquer approach for the analysis of exact algorithms, Journal of the ACM (JACM), vol.56-5, p.25, 2009, ACM.

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
FominGrandoniKratschMaximumindependentSetAlgorithm()

Method Summary

Modifier and Type	Method and Description
it.unimi.dsi.fastutil.ints.IntSet	compute(Grph g)
static void	main(java.lang.String[] args)

Methods inherited from class grph.GrphAlgorithm

cacheResultForGraph, getSourceCode

Methods inherited from class java.lang.Object

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

Constructor Detail

FominGrandoniKratschMaximumindependentSetAlgorithm

public FominGrandoniKratschMaximumindependentSetAlgorithm()

Method Detail

compute

public it.unimi.dsi.fastutil.ints.IntSet compute(Grph g)

Specified by:

compute in class GrphAlgorithm<it.unimi.dsi.fastutil.ints.IntSet>

main

public static void main(java.lang.String[] args)