Как найти максимальный поток в планарном графике?

Question

Я знаю алго, чтобы найти минимальный разрез в планерном графике.

работает как O (NlogN)

Вы создаете двойной график, где каждый Vertice соответствует оригиналу графа фаске и ребро соответствует минимальному ребру, соединяющего два аспекта.

Затем вы используете Dijkstra для поиска минимального пути на этом графике.

Таким образом можно найти минимальный разрез и подсчитать значение расхода.

Но как я могу найти любой из наборов исходных графов графа, которые обеспечивают это значение потока?

Answer 1

Алгоритм, который вы как-то описываете, работает только для неориентированных графов (алгоритм Рейфа). Хасин и Джонсон показали, как это сделать, чтобы вычислить максимальный поток. Недавно было показано, что эти алгоритмы могут быть реализованы в O (n loglog n) времени. См. G. F. Italiano, Y. Nussbaum, P. Sankowski и C. Wulff-Nilsen. Улучшенные алгоритмы для минимальной вырезания и максимального потока в непрямых планарных графах. в Proc. Сорок третий ACM симпозиум по теории вычислений (STOC), Сан-Хосе, 2011.

директивных плоских графам быстрого известный алгоритм работает в O (п § п) см http://web.engr.oregonstate.edu/~glencora/papers/other/Borradaile08-thesis-dissertation.pdf или http://compgeom.cs.uiuc.edu/~jeffe/pubs/parshort.html