Algorithms on Evolving Graphs

Kapre, S (2013) Algorithms on Evolving Graphs. Masters thesis, Indian Institute of Technology Hyderabad.

CS11M1007.pdf - Submitted Version

Download (1MB)


Today's applications process large scale graphs which are evolving in nature. We study new com- putational and data model to study such graphs. In this framework, the algorithms are unaware of the changes happening in the evolving graphs. The algorithms are restricted to probe only lim- ited portion of graph data and are expected to produce a solution close to the optimal one and that too at each time step. This frameworks assumes no constraints on resources like memory and computation time. The limited resource for such algorithms is the limited portion of graph that is allowed to probe (e.g. the number of queries an algorithm can make in order to learn about the graph). We apply this framework to two classical graph theory problems: Shortest Path problem and Maximum Flow problem. We study the way algorithm behaves under evolving model and how does the evolving nature of the graph aects the solution given by the algorithm.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Thesis (Masters)
Uncontrolled Keywords: TD91
Subjects: Computer science > Big Data Analytics
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 07 Nov 2014 04:52
Last Modified: 08 May 2019 11:24
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 621 Statistics for this ePrint Item