Computing exact minimum cuts without knowing the graph

DOI10.4230/LIPICS.ITCS.2018.39MaRDI QIDQ4993305zbMATH OpenFDO

Authors Aviad Rubinstein, Tselil Schramm, S. Matthew Weinberg

Publication date 15 June 2021

Full work available at URL https://arxiv.org/abs/1711.03165

zbMATH Keywords

minimum cutquery complexity

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A new approach to the minimum cut problem
• Practical minimum cut algorithms
• Fundamentals of Computation Theory
• On the Complexity of Finding an Unknown Cut Via Vertex Queries
• Minimum cuts in near-linear time

Cites work

• A new approach to the minimum cut problem
• Deterministic global minimum cut of a simple graph in near-linear time
• Distributed verification and hardness of distributed approximation
• Fast augmenting paths by random sampling from residual graphs
• scientific article; zbMATH DE number 437525 (Why is no real title available?)
• scientific article; zbMATH DE number 3174052 (Why is no real title available?)
• scientific article; zbMATH DE number 5764856 (Why is no real title available?)
• scientific article; zbMATH DE number 177555 (Why is no real title available?)
• scientific article; zbMATH DE number 5485589 (Why is no real title available?)
• On sketching quadratic forms
• On the power of the congested clique model
• Optimally reconstructing weighted graphs using queries
• Random sampling in cut, flow, and network design problems
• Randomized approximation schemes for cuts and flows in capacitated graphs
• Reconstructing weighted graphs with minimal query complexity
• Single pass spectral sparsification in dynamic streams
• Sketching cuts in graphs and hypergraphs
• Sparse reliable graph backbones
• Submodular functions and optimization.
• Subquadratic submodular function minimization
• The ellipsoid method and its consequences in combinatorial optimization
• Twice-Ramanujan sparsifiers

Cited in

(22)

• Intractability of min- and max-cut in streaming graphs
• Faster connectivity in low-rank hypergraphs via expander decomposition
• On the Complexity of Finding an Unknown Cut Via Vertex Queries
• Parameterized query complexity of hitting set using stability of sunflowers
• Query complexity of global minimum cut
• Almost optimal query algorithm for hitting set using a subset query
• Fast algorithms via dynamic-oracle matroids
• Finding a small vertex cut on distributed networks
• Constructing large matchings via query access to a maximal matching oracle
• Polynomial pass semi-streaming lower bounds for k-cores and degeneracy
• On the cut-query complexity of approximating max-cut
• Streaming algorithms for connectivity augmentation
• New lower bounds in Merlin-Arthur communication and graph streaming verification
• Learning-augmented query policies for minimum spanning tree with uncertainty
• Non-adaptive edge counting and sampling via bipartite independent set queries
• Learning spanning forests optimally in weighted undirected graphs with CUT queries
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• Learning partitions using rank queries
• Cut-query algorithms with few rounds
• Almost optimal superconstant-pass streaming lower bounds for reachability
• On triangle estimation using tripartite independent set queries
• Algorithms that access the input via queries

This page was built for publication: Computing exact minimum cuts without knowing the graph

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