On trade-offs in external-memory diameter-approximation

Computing diameters of huge graphs is a key challenge in complex network analysis. However, since exact diameter computation is computationally too costly, one typically relies on approximations. In fact, already a single BFS run rooted at an arbitrary vertex yields a factor two approximation. Unfortunately, in external-memory, even a simple graph traversal like BFS may cause an unacceptable amount of I/O-operations. Therefore, we investigate alternative approaches with worst-case guarantees on both I/O-complexity and approximation factor.