Tight conditional lower bounds for vertex connectivity problems
From MaRDI portal
Cites work
- A note on labeling schemes for graph connectivity
- An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations
- Approximate Gomory–Hu tree is faster than n – 1 max-flows
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Beyond the flow decomposition barrier
- Completeness for first-order properties on sparse structures with algorithmic applications
- Computing Vertex Connectivity: New Bounds from Old Techniques
- Counterexamples for Directed and Node Capacitated Cut-Trees
- Efficient algorithms for clique problems
- Electrical flows, Laplacian systems, and faster approximation of maximum flow in undirected graphs
- Faster algorithms for all-pairs bounded min-cuts
- Maximal Flow Through a Network
- Minimum cuts in near-linear time
- Multi-Terminal Network Flows
- New algorithms and lower bounds for all-pairs max-flow in undirected graphs
- New Algorithms and Lower Bounds for All-Pairs Max-Flow in Undirected Graphs
- On element-connectivity preserving graph simplification
- Rubber bands, convex embeddings and graph connectivity
- Scheduling lower bounds via AND subset sum
- Subcubic equivalences between path, matrix, and triangle problems
- Vertex connectivity in poly-logarithmic max-flows
This page was built for publication: Tight conditional lower bounds for vertex connectivity problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6499310)
