0
喜欢
0
书签
声明论文
Intractability of min- and max-cut in streaming graphs   
摘  要:   We show that the exact computation of a minimum or a maximum cut of a given graph G is out of reach for any one-pass streaming algorithm, that is, for any algorithm that runs over the input stream of G's edges only once and has a working memory of o(n2) bits. This holds even if randomization is allowed.
发  表:   Information Processing Letters  2011

共享有3个版本

Bibtex
创新指数 
阅读指数 
重现指数 
论文点评
还没有人点评哦

Feedback
Feedback
Feedback
我想反馈:
排行榜