Точный плоский электрический поток

22

Рассмотрим электрическую сеть, смоделированную как планарный граф G, где каждое ребро представляет собой резистор 1 Ом. Как быстро мы можем вычислить точное эффективное сопротивление между двумя вершинами в G? Эквивалентно, как быстро мы можем вычислить точный ток, протекающий вдоль каждого края, если мы подключим батарею 1 В к двум вершинам в G?

Известные законы напряжения и тока Кирхгофа сводят эту проблему к решению системы линейных уравнений с одной переменной на ребро. Более поздние результаты, описанные явно Klein и Randić (1993), но неявные в более ранних работах Doyle и Snell (1984), сводят задачу к решению линейной системы с одной переменной на вершину, представляющей потенциал этого узла ; Матрица для этой линейной системы - это матрица Лапласа графа.

Либо линейная система может быть решена именно в время , используя вложенное рассечение и плоские сепараторы [ Lipton Rose Тарьян 1979 ]. Это самый быстрый алгоритм из известных?О(N3/2)

Недавние основополагающие результаты Спилмана, Тенга и других предполагают, что система Лапласа в произвольных графах может быть решена приблизительно в почти линейное время. См. [ Koutis Miller Peng 2010 ] о текущем лучшем времени исполнения и эту удивительную статью Эрики Кларрайх в Simons Foundation для общего обзора. Но меня особенно интересуют точные алгоритмы для плоских графов.

Предположим модель вычисления, которая поддерживает точную действительную арифметику в постоянном времени.

Jeffε
источник
статья Klarreich упоминает о применении (оптимизации) максимального потока вблизи конца и уже устарела из-за недавнего прорыва Орлина , который, по-видимому, не связан с направлением атаки Лапласа. см. также этот недавний вопрос tcs.se. Практичен ли какой-либо из современных алгоритмов максимального потока? О(мN)
ВЗН

Ответы:

14

О(Nω)

О(Nω)

A.Schulz
источник