Min st-Cut of a Planar Graph in O(n loglog n) Time
classification
💻 cs.DM
keywords
timegivengraphloglogplanarst-cutbestbound
read the original abstract
Given a planar undirected n-vertex graph G with non-negative edge weights, we show how to compute, for given vertices s and t in G, a min st-cut in G in O(n loglog n) time and O(n) space. The previous best time bound was O(n log n).
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.