Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
From MaRDI portal
Publication:4962174
DOI10.1145/2684068zbMath1398.68217OpenAlexW1980410492MaRDI QIDQ4962174
Piotr Sankowski, Christian Wulff-Nilsen, Glencora Borradaile
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/2684068
Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (9)
Some insights on dynamic maintenance of Gomory-Hu tree in cactus graphs and general graphs ⋮ Unnamed Item ⋮ Faster shortest paths in dense distance graphs, with applications ⋮ Minimum Cuts and Shortest Cycles in Directed Planar Graphs via Noncrossing Shortest Paths ⋮ Unnamed Item ⋮ Near-linear time constant-factor approximation algorithm for branch-decomposition of planar graphs ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Unnamed Item
This page was built for publication: Min st -Cut Oracle for Planar Graphs with Near-Linear Preprocessing Time
