Forewarned Is Fore-Armed: Dynamic Digraph Connectivity with Lookahead Speeds Up a Static Clustering Algorithm

摘要

Dynamic data structures are presented for directed graphs that maintain (a) Transitive Closure and (b) Decomposition into Strongly Connected Components in a "semi-online" situation which improve the static algorithms for minimum sum-of-diameters clustering are improved by a O(log n) factor.