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