Intractability of min- and max-cut in streaming graphs

DOI10.1016/j.ipl.2010.10.017zbMath1259.05175MaRDI QIDQ1944060

Mariano Zelke

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

zbMATH Keywords

minimum cut; maximum cut; graph algorithms; intractability; streaming algorithms; max-cut; min-cut

Mathematics Subject Classification ID

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