greedy_mis

iqm.applications.mis.greedy_mis(mis_problem)

Standard greedy algorithm for maximum independent set problem class.

Steps:

1. Pick the lowest-degree node in the graph.

2. Add it to the independent set.

3. Remove it and all its neighbors from the graph.

4. Repeat steps 1-3 until the graph is empty.

5. Return the independent set.

Parameters:

mis_problem (MISInstance | Graph) – A problem instance of maximum independent set or a Graph.

Returns:

A bitstring solution.

Return type:

str