Near-optimal distributed computation of small vertex cuts
From MaRDI portal
Publication:6579850
DOI10.1007/s00446-023-00455-zMaRDI QIDQ6579850
Publication date: 26 July 2024
Published in: Distributed Computing (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Packet routing and job-shop scheduling in \(O\) (congestion + dilation) steps
- A data structure for dynamic trees
- On-line maintenance of triconnected components with SPQR-trees
- Random Sampling in Cut, Flow, and Network Design Problems
- Near-Optimal Scheduling of Distributed Algorithms
- Construction and Impromptu Repair of an MST in a Distributed Network with o(m) Communication
- Dual Failure Resilient BFS Structure
- Pseudorandomness
- Replacement Paths and Distance Sensitivity Oracles via Fast Matrix Multiplication
- Distributed connectivity decomposition
- Spanners and sparsifiers in dynamic streams
- Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
- Fast computation of small cuts via cycle space sampling
- 2-Vertex Connectivity in Directed Graphs
- Distributed Computing: A Locality-Sensitive Approach
- Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut
- Connectivity Oracles for Graphs Subject to Vertex Failures
- Dividing a Graph into Triconnected Components
- Multiple Source Dual Fault Tolerant BFS Trees
- Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
- Breaking quadratic time for small vertex connectivity and an approximation scheme
- MST in Log-Star Rounds of Congested Clique
- Depth-First Search and Linear Graph Algorithms
- Dynamic graph connectivity in polylogarithmic worst case time
- Otakar Borůvka on minimum spanning tree problem. Translation of both the 1926 papers, comments, history
- Distributed weighted min-cut in nearly-optimal time
- Near-Linear-Time, Optimal Vertex Cut Sparsifiers in Directed Acyclic Graphs
- Vertex connectivity in poly-logarithmic max-flows
- Fault-Tolerant Labeling and Compact Routing Schemes
- Small cuts and connectivity certificates: a fault tolerant approach
- Distributed constructions of dual-failure fault-tolerant distance preservers
This page was built for publication: Near-optimal distributed computation of small vertex cuts
