Dynamizing Graph Classes and Output Sensitive Fault Tolerant Subgraph Problems [HBNI Th198]

Abstract

To analyze an algorithm for a graph problem the traditional notion is to assume that a graph is static. However, for most real world applications graphs are constantly modified. These modifications can be in terms of edge/vertex insertions or deletions or both. Two different models that study and analyze graphs in this setting are dynamic algorithms and fault tolerant algorithms. The aim is to maintain some property of the ever changing graph faster than the corresponding static algorithm. We will look at several classical graph problems and give upper and lower bounds for them in both the dynamic and the fault tolerant subgraph model.