-1
$\begingroup$

I have an undirected graph G with a set of vertices and edges. Each vertex has a weight w. Let's assume we have all vertices connected with some paths. I'm looking for a variant of the min-cut problem. I search for a subdivision of the graph into two parts which are connected by a group of vertices which weights sum up to a minimum value. Can you give me a pointer or a name to the problem (if it exists already)?

$\endgroup$
3
$\begingroup$

This problem is called weighted vertex connectivity. See for instance "Computing Vertex Connectivity: New Bounds from Old Techniques" by Henzinger, Rao and Gabow (link).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.