Optimal per-edge processing times in the semi-streaming model
From MaRDI portal
Publication:2380006
DOI10.1016/j.ipl.2007.06.004zbMath1183.05087arXiv0708.4284MaRDI QIDQ2380006
Publication date: 24 March 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0708.4284
68R10: Graph theory (including graph drawing) in computer science
05C85: Graph algorithms (graph-theoretic aspects)
Related Items
Intractability of min- and max-cut in streaming graphs, Weighted matching in the semi-streaming model
Cites Work
- 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
- An optimal minimum spanning tree algorithm
- Using expander graphs to find vertex connectivity
- Sparsification—a technique for speeding up dynamic graph algorithms
- A minimum spanning tree algorithm with inverse-Ackermann type complexity
- Weighted Matching in the Semi-Streaming Model
- Automata, Languages and Programming
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item