CODEWITHSUNDEEP
c++algorithmgraphdiscrete-mathematics
Noob Coder
Noob Coder

Reputation: 244

Splitting Graph into 2

How can we split a weighted graph into 2 equal halves(both halves containing the same number of vertices) such that the total sum of removing edges in minimum?

Upvotes: 2

Views: 845

Answers (1)

bg2b
bg2b

Reputation: 1979

The problem you're considering falls under the heading of "graph partitioning". Almost any variant is at least NP-complete (unless your graphs have some special properties that help you out), so you'll probably have to resort to approximate heuristics if your graph is of nontrivial size. From a practical point of view, I'd suggest just using some existing libraries. The Wikipedia page gives a list of open-source packages, at least some of which are very sophisticated.

http://en.wikipedia.org/wiki/Graph_partition

Upvotes: 3

Related Questions