On Graph Problems in a Semi-streaming Model Export

@incollection{citeulike:1300860, abstract = {We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, the input graph, G=( V, E), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by O( n⋅polylog n), where n = | V|. We are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. In the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithm improvement for the bipartite case. We also exhibit log n/log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. These are complemented by Ω (log (1– ε) n) lower bounds.}, author = {Feigenbaum, Joan and Kannan, Sampath and Mcgregor, Andrew and Suri, Siddharth and Zhang, Jian}, citeulike-article-id = {1300860}, citeulike-linkout-0 = {http://www.springerlink.com/content/qr7h100awelu6hkc}, journal = {Automata, Languages and Programming}, keywords = {algorithm, bound, diameter, lower, semi-streaming, streaming}, pages = {531--543}, posted-at = {2007-05-16 22:41:48}, priority = {0}, title = {On Graph Problems in a Semi-streaming Model}, url = {http://www.springerlink.com/content/qr7h100awelu6hkc}, year = {2004} }

TY - CHAP ID - citeulike:1300860 L3 - citeulike-article-id:1300860 N2 - We formalize a potentially rich new streaming model, the semi-streaming model, that we believe is necessary for the fruitful study of efficient algorithms for solving problems on massive graphs whose edge sets cannot be stored in memory. In this model, the input graph, G=( V, E), is presented as a stream of edges (in adversarial order), and the storage space of an algorithm is bounded by O( n⋅polylog n), where n = | V|. We are particularly interested in algorithms that use only one pass over the input, but, for problems where this is provably insufficient, we also look at algorithms using constant or, in some cases, logarithmically many passes. In the course of this general study, we give semi-streaming constant approximation algorithms for the unweighted and weighted matching problems, along with a further algorithm improvement for the bipartite case. We also exhibit log n/log log n semi-streaming approximations to the diameter and the problem of computing the distance between specified vertices in a weighted graph. These are complemented by Ω (log (1– ε) n) lower bounds. JF - Automata, Languages and Programming EP - 543 TI - On Graph Problems in a Semi-streaming Model SP - 531 KW - algorithm KW - bound KW - diameter KW - lower KW - semi-streaming KW - streaming AU - Feigenbaum, Joan AU - Kannan, Sampath AU - Mcgregor, Andrew AU - Suri, Siddharth AU - Zhang, Jian PY - 2004/// UR - http://www.springerlink.com/content/qr7h100awelu6hkc ER -