Intractability of min- and max-cut in streaming graphs
From MaRDI portal
Publication:1944060
DOI10.1016/j.ipl.2010.10.017zbMath1259.05175MaRDI QIDQ1944060
Publication date: 4 April 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.686.4740
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
Cites Work
- Streaming algorithm for graph spanners-single pass and constant processing time per edge
- On finding common neighborhoods in massive graphs.
- A matroid approach to finding edge connectivity and packing arborescences
- Optimal per-edge processing times in the semi-streaming model
- IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
- Maximal Flow Through a Network
- Graph Sparsification in the Semi-streaming Model
- An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Communication Complexity
- Weighted Matching in the Semi-Streaming Model
- Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
- Some optimal inapproximability results
- On Estimating Path Aggregates over Streaming Graphs
- Automata, Languages and Programming
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- Computing and Combinatorics
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item