An Algorithm for Partitioning the Nodes of a Graph

Let G = \ N,E \ be an undirected graph having nodes N and edges E. We consider the problem of partitioning N into k disjoint subsets N₁ , ⋯ ,Nₖ of given sizes m₁ , ⋯ ,mₖ, respectively, in such a way that the number of edges in E that connect different subsets is minimal. We obtain a heuristic solution from the solution of a linear programming transportation problem.