Finding a small vertex cut on distributed networks

Cites work

scientific article; zbMATH DE number 1256717 (Why is no real title available?)
A SubLinear Time Distributed Algorithm for Minimum-Weight Spanning Trees
A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
A faster distributed protocol for constructing a minimum spanning tree
A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning
A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
A probabilistic algorithm for vertex connectivity of graphs
Almost-Tight Distributed Minimum Cut Algorithms
An Algorithm for Determining Whether the Connectivity of a Graph is at Leastk
Breaking quadratic time for small vertex connectivity and an approximation scheme
Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
Computing Vertex Connectivity: New Bounds from Old Techniques
Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
Computing exact minimum cuts without knowing the graph
Depth-First Search and Linear Graph Algorithms
Deterministic global minimum cut of a simple graph in near-linear time
Distributed Approximation of Minimum k-edge-connected Spanning Subgraphs
Distributed approximation algorithms for weighted shortest paths
Distributed edge connectivity in sublinear time
Distributed minimum cut approximation
Distributed triangle detection via expander decomposition
Distributed verification and hardness of distributed approximation
Distributed weighted min-cut in nearly-optimal time
Dividing a Graph into Triconnected Components
Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and \(O(n^{1/2-\epsilon})\)-time
Efficient randomized distributed coloring in CONGEST
Expander decomposition and pruning: faster, stronger, and simpler
Fast Distributed Construction of Smallk-Dominating Sets and Applications
Fast computation of small cuts via cycle space sampling
Fast routing table construction using small messages (extended abstract)
Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
Fully-dynamic minimum spanning forest with improved worst-case update time
Improved Distributed Approximations for Minimum-Weight Two-Edge-Connected Spanning Subgraph
Improved algorithms for graph four-connectivity
Improved distributed algorithms for exact shortest paths
Improved distributed expander decomposition and nearly optimal triangle enumeration
Local flow partitioning for faster edge connectivity
Minimum cuts in near-linear time
Near-optimal distributed maximum flow
Near-optimal distributed maximum flow (extended abstract)
Near-optimal scheduling of distributed algorithms
Network Flow and Testing Graph Connectivity
On the cut dimension of a graph
Rubber bands, convex embeddings and graph connectivity
Small cuts and connectivity certificates: a fault tolerant approach
Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search
Testing 2-vertex connectivity and computing pairs of vertex-disjoint \(s\)-\(t\) paths in digraphs
Universally-optimal distributed algorithms for known topologies
Using expander graphs to find vertex connectivity
Vertex connectivity in poly-logarithmic max-flows
Voronoi diagrams on planar graphs, and computing the diameter in deterministic \(\tilde{O}(n^{5/3})\) time
Weighted min-cut: sequential, cut-query, and streaming algorithms

This page was built for publication: Finding a small vertex cut on distributed networks

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