Intractability of min- and max-cut in streaming graphs
type: Item
instance of: scholarly article
title: Intractability of min- and max-cut in streaming graphs
zbMATH Open document ID: 1259.05175
author: Mariano Zelke
published in: Information Processing Letters
publication date: 2013-04-04T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6150244
zbMATH Keywords: graph algorithms
zbMATH Keywords: streaming algorithms
zbMATH Keywords: intractability
zbMATH Keywords: minimum cut
zbMATH Keywords: min-cut
zbMATH Keywords: maximum cut
zbMATH Keywords: max-cut
MaRDI profile type: Publication
OpenAlex ID: W2060383163
cites work: Graph Sparsification in the Semi-streaming Model
cites work: Q4091421
cites work: An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
cites work: Q4828992
cites work: Streaming algorithm for graph spanners-single pass and constant processing time per edge
cites work: Q4228453
cites work: On finding common neighborhoods in massive graphs.
cites work: Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners
cites work: IMPROVED APPROXIMATION GUARANTEES FOR WEIGHTED MATCHING IN THE SEMI-STREAMING MODEL *
cites work: Automata, Languages and Programming
cites work: Graph distances in the streaming model: the value of space
cites work: Maximal Flow Through a Network
cites work: A matroid approach to finding edge connectivity and packing arborescences
cites work: On Estimating Path Aggregates over Streaming Graphs
cites work: Q4198056
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Some optimal inapproximability results
cites work: Q4945538
cites work: Computing and Combinatorics
cites work: Q4142699
cites work: Communication Complexity
cites work: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
cites work: Q3425115
cites work: Optimal per-edge processing times in the semi-streaming model
cites work: Weighted Matching in the Semi-Streaming Model
DOI: 10.1016/J.IPL.2010.10.017
description: scientific article; zbMATH DE number 6150244