Finding a small vertex cut on distributed networks

Cites Work

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

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)