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

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 полной в целом и имеет алгоритмы приближения логарифмического коэффициента. Если im верно, то это слабо NP трудно в плоских графах с 2-мерным алгоритмом nawen garg. (Chk it on google)

Answer 2

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