Independent Set¶

Algorithms¶

The following algorithms are available:

jgrapht.algorithms.independent.chordal_max_independent_set(graph)[source]¶

Find a maximum independent set in a chordal graph.

The algorithms first computes a perfect elimination ordering and then a maximum independent set. Running time \(\mathcal{O}(n+m)\).

Parameters: graph – the chordal graph. If the graph is not chordal an error is raised
Returns: an independent set as a vertex set