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
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
Distributed connectivity decomposition
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
Title not available (Why is that?)
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
Distributed exact shortest paths in sublinear time
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 - ε})-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)