Optimal per-edge processing times in the semi-streaming model

DOI10.1016/j.ipl.2007.06.004zbMath1183.05087arXiv0708.4284OpenAlexW1988627162MaRDI QIDQ2380006

Mariano Zelke

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

zbMATH Keywords

graph algorithmsstreaming algorithmsper-edge processing time

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (2)

Weighted matching in the semi-streaming model ⋮ Intractability of min- and max-cut in streaming graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: Optimal per-edge processing times in the semi-streaming model