Algorytmy grafowe w modelu półstrumieniowym

W pracy zostaną zaprezentowane algorytmy w stosunkowo nowym modelu nazwanym modelem półstrumieniowym. Głównym założeniem tego modelu jest, że cały graf nie może zostać przechowany w pamięci i możemy użyć tylko O(n polylog n) bitów. Wejście jest zaprezentowane jako strumień krawędzi. Pokazujemy algorytmy na dwudzielność, minimalne drzewo rozpinające, znajdowanie punktów artykulacji, maksymalne skojarzenie w grafach dwudzielnych, maksymalne skojarzenie ważone i spaner grafu. Dostarczamy kilka lematów pokazujących co jest możliwe lub niemożliwe w modelu półstrumieniowym. Przeprowadzamy również eksperymentalne porównanie algorytmów na spanery.

This paper presents graph algorithms in relatively new model called the semi-streaming model. The main idea is that the entire graph cannot be stored in the memory and we can use only O(n polylog n) bits. The input is presented as a stream of edges. We show algorithms for bipartiteness, the minimum spanning tree problem, finding articulation points, the maximum matching problem in bipartite graphs, the maximum weighted matching problem and graph spanners. We provide a couple of lemmas showing what can or cannot be done in the semi-streaming model. We also make an experimental comparison of the algorithms for spanners.