Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
Min st-cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
For an undirected n-vertex planar graph G with non-negative edge-weights, we consider the following type of query: given two vertices s and t in G, what is the weight of a min st-cut in G? We show how to answer such queries in constant time with O(n log <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" …