Name
Abstract | ||
|---|---|---|
Motivated by applications that concern graphs that are evolving and massive in nature, we define a new general framework for computing with such graphs. In our framework, the graph changes over time and an algorithm can only track these changes by explicitly probing the graph. This framework captures the inherent tradeoff between the complexity of maintaining an up-to-date view of the graph and the quality of results computed with the available view. We apply this framework to two classical graph connectivity problems, namely, path connectivity and minimum spanning trees, and obtain efficient algorithms. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1145/2090236.2090249 | ITCS |
Keywords | Field | DocType |
inherent tradeoff,concern graph,new general framework,graph change,classical graph connectivity problem,up-to-date view,efficient algorithm,path connectivity,available view,algorithms,graph connectivity,minimum spanning tree | Block graph,Modular decomposition,Outerplanar graph,Comparability graph,Line graph,Algorithm,Graph product,Pathwidth,Mathematics,Graph (abstract data type) | Conference |
Citations | PageRank | References |
13 | 0.74 | 9 |
Authors | ||
5 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Aris Anagnostopoulos | 1 | 1054 | 67.08 |
| Ravi Kumar | 2 | 13932 | 1642.48 |
| Mohammad Mahdian | 3 | 2689 | 226.62 |
| Eli Upfal | 4 | 4310 | 743.13 |
| Fabio Vandin | 5 | 218 | 27.55 |