Abstract:
Graph is a popular model to represent highly structured data which involves entities
who have pairwise relations between them. In many applications, computing graph
theoretic properties after modelling the entire dataset as graph, provides us interesting
informations which gives us insights about the whole dataset. However, in case of
application, the datasets in question can be so large that it's di cult to store in the
main memory and the dataset can even be dynamic(can change with time). These
days in so many applications, the algorithm that requires to solve the problem which
takes massive dataset as input, has limitations on time as well as space taken to store
the information. These constraints leads us for the development of new techniques.
Streaming model of computation takes all these challenges into account and provides
us solutions with limited resources in cost of accuracy. Graph stream is a sequence of
imcoming edges and we are only allowed to insert(insertion only model) or both insert
and delete(dynamic model) into an initially empty graph. Finally our objective is to
nd out certain properties of the graph at the end of the stream which minimizes the
amount of space the algorithm uses. Sometimes this algorithm needs to provide the
trade of between the space usage and the time taken.
There is a large volume work on undirected graphs in streaming model but the area of
directed graph stream is a pretty unexplored. In this project, we study the problem
of testing acyclicity in dense digraphs in semi-streaming model. Here the graph on n
vertices is presented as a stream of edges and using O(n polylog(n))-space, we must
determine if it is acyclic or not
