Помогите решить следующую задачу.
Есть граф, вершины и ребра которого взвешаны целыми числами. Необходимо разбить этот граф на части, минимально связанные между собой. Причем число вершин в каждом "куске" графа и суммарный вес не должны превышать заданных значений.

Заранее благодарен за отвен.

P.S. Неплого если алгоримт можно было бы распараллелить.