Streaming algorithms for network design
From MaRDI portal
Cites work
- A (1.5+)-approximation algorithm for weighted connectivity augmentation
- A 4+ approximation for k-connected subgraphs
- A better-than-2 approximation for weighted tree augmentation
- A factor 2 approximation algorithm for the generalized Steiner network problem
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- A primal-dual approximation algorithm for generalized Steiner network problems
- A simple semi-streaming algorithm for global minimum cuts
- A Trivial Yet Optimal Solution to Vertex Fault Tolerant Spanners
- An improved approximation algorithm for the minimum cost subset \(k\)-connected subgraph problem
- An O(k^3 log n)-Approximation Algorithm for Vertex-Connectivity Survivable Network Design
- Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
- Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Approximating minimum-cost edge-covers of crossing biset-families
- Approximation Algorithms for Graph Augmentation
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Biconnectivity approximations and graph carvings
- Breaching the 2-approximation barrier for connectivity augmentation: a reduction to Steiner tree
- Bridging the gap between tree and connectivity augmentation: unified and stronger approaches
- Dividing a Graph into Triconnected Components
- Dynamic Graphs in the Sliding-Window Model
- Efficient and Simple Algorithms for Fault-Tolerant Spanners
- Erratum: ``Approximating minimum-cost connectivity problems via uncrossable bifamilies
- Fast and Space Efficient Spectral Sparsification in Dynamic Streams
- Graph Distances in the Data-Stream Model
- Graph Sparsification in the Semi-streaming Model
- scientific article; zbMATH DE number 1003253 (Why is no real title available?)
- scientific article; zbMATH DE number 5485528 (Why is no real title available?)
- scientific article; zbMATH DE number 2080088 (Why is no real title available?)
- scientific article; zbMATH DE number 1775403 (Why is no real title available?)
- scientific article; zbMATH DE number 1405806 (Why is no real title available?)
- scientific article; zbMATH DE number 7053293 (Why is no real title available?)
- scientific article; zbMATH DE number 7788450 (Why is no real title available?)
- scientific article; zbMATH DE number 7788451 (Why is no real title available?)
- scientific article; zbMATH DE number 7788512 (Why is no real title available?)
- Improved approximation algorithms for minimum cost node-connectivity augmentation problems
- Improved Approximation for Two-Edge-Connectivity
- Intractability of min- and max-cut in streaming graphs
- Iterative rounding 2-approximation algorithms for minimum-cost vertex connectivity problems
- Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
- Local search for weighted tree augmentation and Steiner tree
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- Network design via iterative rounding of setpair relaxations
- On data structures and asymmetric communication complexity
- On estimating maximum matching size in graph streams
- On graph problems in a semi-streaming model
- On sparse spanners of weighted graphs
- On-line maintenance of triconnected components with SPQR-trees
- On-Line Planarity Testing
- Optimal lower bounds for distributed and streaming spanning forest computation
- Optimal Vertex Fault Tolerant Spanners (for fixed stretch)
- Partially optimal edge fault-tolerant spanners
- Scan-First Search and Sparse Certificates: An Improved Parallel Algorithm for k-Vertex Connectivity
- Single pass spectral sparsification in dynamic streams
- Spanners and sparsifiers in dynamic streams
- Spectral sparsification in the semi-streaming setting
- Steiner tree approximation via iterative randomized rounding
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Streaming algorithms for connectivity augmentation
- Streaming algorithms for geometric Steiner forest
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Streaming Lower Bounds for Approximating MAX-CUT
- Superlinear lower bounds for multipass graph processing
- Tight bounds for graph problems in insertion streams
- Tight bounds for vertex connectivity in dynamic streams
This page was built for publication: Streaming algorithms for network design
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7346828)
