Module max_cut 

Maximum cut algorithms (ALGO-FL-002).

A cut of a graph partitions the vertices into two disjoint sets (S, V\S). The cut value is the number (or total weight) of edges crossing the partition. Finding a maximum cut is NP-hard; we provide a greedy 0.5-approximation.

The greedy algorithm processes vertices in order, assigning each to the side that maximizes the number of crossing edges. This guarantees a cut of at least |E|/2.

Structs

MaxCutResult

Result of maximum_cut.

Functions

cut_value

Compute the cut value for a given vertex partition.

maximum_cut

Compute an approximate maximum cut using a greedy heuristic.