Efficient contractions of dynamic graphs -- with applications
From MaRDI portal
Cites work
- A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond
- A general framework for graph sparsification
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A near-linear time algorithm for constructing a cactus representation of minimum cuts
- Algorithmic Aspects of Graph Connectivity
- Cactus representation of minimum cuts: derandomize and speed up
- Compact cactus representations of all non-trivial min-cuts
- Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
- Constructing linear-sized spectral sparsification in almost-linear time
- Deterministic Edge Connectivity in Near-Linear Time
- Dynamic graph connectivity in polylogarithmic worst case time
- Faster algorithms for computing maximal 2-connected subgraphs in sparse directed graphs
- Faster Algorithms for Edge Connectivity via Random 2-Out Contractions
- Finding 2-edge and 2-vertex strongly connected components in quadratic time
- Fully dynamic exact edge connectivity in sublinear time
- Fully-dynamic min-cut
- Graph sparsification by effective resistances
- scientific article; zbMATH DE number 1256718 (Why is no real title available?)
- Local flow partitioning for faster edge connectivity
- Maximal k-edge-connected subgraphs in almost-linear time for small k
- Maximal \(k\)-edge-connected subgraphs in weighted graphs via local random contraction
- Minimum cuts in near-linear time
- Optimal decremental connectivity in non-sparse graphs
- Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
- Randomized approximation schemes for cuts and flows in capacitated graphs
- Spectral sparsification of graphs
- Twice-Ramanujan sparsifiers
This page was built for publication: Efficient contractions of dynamic graphs -- with applications
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322429)
