| Calling Sequence | MaxCut(G)
MaxCut(G,weighted) | ||||||||||||
| Parameters |
| ||||||||||||
| Return Type | list ([set,set,numeric]) | ||||||||||||
| Synopsis | MaxCut is the problem of computing the maximum cut of a undirected graph G(V,E), i.e., that of partitioning the vertex set V into two parts so that the number (resp. weights) of edges joining vertices in different parts is as large as possible. It is known to be NP-hard. | ||||||||||||
This greedy approximation algorithm solves the unweighted MaxCut problem in O(e+n) (weighted O(e*log(e)+n)) and is a 1/2+1/(2n) approximation. The weighted form of the algorithm expects numeric Label fields in the graph data-structure. | |||||||||||||
The algortihm returns the two disjoint vertex sets and the number (resp. weights) of the edges crossing the two sets. | |||||||||||||
| Examples | > G := Rand(Graph): > MaxCut(G); [{2,5,7,9,10}, {1,3,4,6,8}, 15]
| ||||||||||||
| See also | BipartiteGraph, Clique, DrawGraph, Edge, EdgeComplement, Edges, FindConnectedComponents, Graph, Graph_Rand, InduceGraph, MaxEdgeWeightClique, MST, Nodes, Path, RegularGraph, ShortestPath, TetrahedronGraph, VertexCover | ||||||||||||