Взвешенное разбиение неориентированных графов

Question

Для неориентированного циклического плоского графа G (V, E) с весами вершин W (V), фиксированной плоскостью, в которую вкладываются E (G) и двумя узлами s и t, мне нужно найти разбиение G, которое делит его надва соединенных компонента S (G) и T (G), где s находится в S (G), а t находится в T (G).Вершины s и t принадлежат внешней грани вложения E (G).

Я хочу, чтобы разбиения были хорошо сбалансированы - они должны иметь почти равные суммы весов вершин.

Любыеидеи для хорошего алгоритма, пожалуйста?

Answer 1

Это какая-то проблема сбалансированного разреза, которая является NP Complete в целом и имеет алгоритмы приближения логарифмического фактора. Если я прав, то это слабо NP трудно в плоских графах с алгоритмом 2 приблизительно по Naveen Garg. (Chk это на Google)

Answer 2

Вычислить минимальное связующее дерево и использовать вместе со свойствами балансировки AVL-дерева?