Space complexity of vertex connectivity oracles
From MaRDI portal
Cites work
- 2-Edge Connectivity in Directed Graphs
- 2-vertex connectivity in directed graphs
- A graph reduction step preserving element-connectivity and packing Steiner trees and forests
- 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
- A note on a recent algorithm for minimum cut
- A note on labeling schemes for graph connectivity
- A primal–dual schema based approximation algorithm for the element connectivity problem
- A simple deterministic algorithm for edge connectivity
- An O(k^3 n)-approximation algorithm for vertex-connectivity survivable network design
- An inverse-Ackermann type lower bound for online minimum spanning tree verification
- An optimal labeling for node connectivity
- Ancestor tree for arbitrary multi-terminal cut functions
- Approximate Gomory–Hu tree is faster than n – 1 max-flows
- Bottlenecks and Edge Connectivity in Unsymmetrical Networks
- Breaking the cubic barrier for all-pairs max-flow: Gomory-Hu tree in nearly quadratic time
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
- Computing on a free tree via complexity-preserving mappings
- Counterexamples for Directed and Node Capacitated Cut-Trees
- Data structures for node connectivity queries
- Deformable Polygon Representation and Near-Mincuts
- Deterministic minimum cut in poly-logarithmic maximum flows
- Efficient algorithms for computing all low s-t edge connectivities and related problems
- Efficient algorithms for generalized cut‐trees
- Extracting maximal information about sets of minimum cuts
- Faster algorithms for all-pairs bounded min-cuts
- Flow trees for vertex-capacitated networks
- Graph connectivities, network coding, and expander graphs
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 432789 (Why is no real title available?)
- scientific article; zbMATH DE number 1261811 (Why is no real title available?)
- scientific article; zbMATH DE number 1263227 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 910886 (Why is no real title available?)
- scientific article; zbMATH DE number 3314878 (Why is no real title available?)
- Introduction to Random Graphs
- Labeling Schemes for Flow and Connectivity
- Labeling schemes for vertex connectivity
- Maximum flow and minimum-cost flow in almost-linear time
- Minimum cost flows, MDPs, and ℓ 1 -regression in nearly linear time for dense instances
- Minimum cut in O(m^2 n time
- Minimum cuts in near-linear time
- Multi-Terminal Network Flows
- On Cartesian Trees and Range Minimum Queries
- On element-connectivity preserving graph simplification
- On mixed connectivity certificates
- On sparse subgraphs preserving connectivity properties
- On-line maintenance of triconnected components with SPQR-trees
- Reinventing the wheel
- Strong articulation points and strong bridges in large scale graphs
- The connectivity carcass of a vertex subset in a graph and its incremental maintenance
- The General Structure of Edge-Connectivity of a Vertex Subset in a Graph and its Incremental Maintenance. Odd Case
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Vertex connectivity in poly-logarithmic max-flows
- Weighted min-cut: sequential, cut-query, and streaming algorithms
- Zur allgemeinen Kurventheorie.
This page was built for publication: Space complexity of vertex connectivity oracles
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6846212)
