Title: On sublinear algorithms for approximating graph parameters
Speaker: Dana Ron, Tel-Aviv University
Date: Wednesday, October 19, 2011 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
When we refer to efficient algorithms, we usually mean polynomial-time algorithms. In particular this is true for graph algorithms, which are considered efficient if they run in time polynomial in the number of vertices and edges of the graph.
However, in some cases we may seek even more efficient algorithms whose running time is sublinear in the size of the input graph. Such algorithms do not even read the whole input graph, but rather sample random parts of the graph and compute approximations of various parameters of interest.
In this talk I will survey various such algorithms, where the parameters I will discuss are:
(1) The average degree the number of small stars (2) The weight of a minimum spanning tree (3) The size of a minimum vertex cover and a maximum matching (4) The number of edges that should be added/removed in order to obtain various properties