Streaming algorithms for connectivity augmentation
From MaRDI portal
Cites work
- A (1.5+)-approximation algorithm for weighted connectivity augmentation
- A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- 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 matroid approach to finding edge connectivity and packing arborescences
- A near-linear time algorithm for constructing a cactus representation of minimum cuts
- A primal-dual approximation algorithm for generalized Steiner network problems
- A simple semi-streaming algorithm for global minimum cuts
- A simplified 1.5-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2
- An approximation for finding a smallest 2-edge-connected subgraph containing a specified spanning tree
- Approximating k-node Connected Subgraphs via Critical Graphs
- Approximating minimum-cost \(k\)-node connected subgraphs via independence-free graphs
- Approximating Steiner networks with node-weights
- Approximation Algorithms for Graph Augmentation
- Approximation algorithms for Steiner tree augmentation problems
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Automata, Languages and Programming
- 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
- Computing exact minimum cuts without knowing the graph
- Dynamic Graphs in the Sliding-Window Model
- Fast and Space Efficient Spectral Sparsification in Dynamic Streams
- Graph Distances in the Data-Stream Model
- Graph spanners: a tutorial review
- scientific article; zbMATH DE number 1003253 (Why is no real title available?)
- scientific article; zbMATH DE number 5485526 (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?)
- Improved approximation for tree augmentation: saving by rewiring
- Improved Approximation for Two-Edge-Connectivity
- Intractability of min- and max-cut in streaming graphs
- Local search for weighted tree augmentation and Steiner tree
- Maximum matchings in dynamic graph streams and the simultaneous communication model
- Node-weighted Network Design in Planar and Minor-closed Families of Graphs
- On estimating maximum matching size in graph streams
- On the cycle augmentation problem: hardness and approximation algorithms
- Optimal lower bounds for distributed and streaming spanning forest computation
- Prize-collecting survivable network design in node-weighted graphs
- Single pass spectral sparsification in dynamic streams
- Spanners and sparsifiers in dynamic streams
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners
- Superlinear lower bounds for multipass graph processing
- Tight bounds for graph problems in insertion streams
This page was built for publication: Streaming algorithms for connectivity augmentation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6875101)
