Min <i>st</i> -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
Min <i>st</i> -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
For an undirected n -vertex planar graph G with nonnegative 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 …