scientific article; zbMATH DE number 6850341

MaRDI QIDQ4607913zbMATH OpenFDO

Authors Shay Mozes, Kirill Nikolaev, Yahav Nussbaum, Oren Weimann

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/1512.02068, http://dl.acm.org/citation.cfm?id=3175302

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Min-cuts and shortest cycles in planar graphs in O(n n) time
• scientific article; zbMATH DE number 6469225
• scientific article; zbMATH DE number 60387
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• Polynomial-time approximation scheme for minimum \(k\)-cut in planar and minor-free graphs
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• Minimum Cuts of Simple Graphs in Almost Always Linear Time
• A note on finding minimum cuts in directed planar networks by parallel computations
• A Faster Algorithm for Finding the Minimum Cut in a Directed Graph

Cited in

(23)

• A note on finding minimum cuts in directed planar networks by parallel computations
• Faster shortest paths in dense distance graphs, with applications
• A semantic relatedness preserved subset extraction method for language corpora based on pseudo-Boolean optimization
• Topologically trivial closed walks in directed surface graphs
• An efficient cutting plane algorithm for the minimum weighted elementary directed cycle problem in planar digraphs
• Minimum cuts and shortest cycles in directed planar graphs via noncrossing shortest paths
• Min-cuts and shortest cycles in planar graphs in O(n n) time
• Minimum s-t cut in undirected planar graphs when the source and the sink are close
• scientific article; zbMATH DE number 60387 (Why is no real title available?)
• The All-Pairs Min Cut Problem and the Minimum Cycle Basis Problem on Planar Graphs
• Min \(st\)-cut oracle for planar graphs with near-linear preprocessing time
• Improved bounds for shortest paths in dense distance graphs
• Triangles and girth in disk graphs and transmission graphs
• Recognizing planar Laman graphs
• Topologically trivial closed walks in directed surface graphs
• Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
• scientific article; zbMATH DE number 2188469 (Why is no real title available?)
• scientific article; zbMATH DE number 6469225 (Why is no real title available?)
• Minimum Cuts in Surface Graphs
• Almost optimal exact distance oracles for planar graphs
• Fully dynamic algorithms for minimum weight cycle and related problems
• Faster construction of a planar distance oracle with \(\tilde{O}(1)\) query time
• A fast algorithm for minimum weight odd circuits and cuts in planar graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607913)