patternMinor
Graph partitioning with parts of equal size
Viewed 0 times
graphwithequalsizepartspartitioning
Problem
Partition an undirected graph of $n$ nodes into $k$ subgraphs so that total vertices inside all subgraphs is maximum.
Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$); $k$ is given initially.
I'd like to receive pointers to the solution as well as papers or blogs related to or expanding on it.
Restriction: all subgraphs have the same number of nodes (so $k$ divides $n$); $k$ is given initially.
I'd like to receive pointers to the solution as well as papers or blogs related to or expanding on it.
Solution
Your problem is a special case of graph partitioning. When $k=2$, the problem is known as minimum bisection, and is NP-complete.
Context
StackExchange Computer Science Q#104596, answer score: 2
Revisions (0)
No revisions yet.