DYNAMIC DIGRAPH CONNECTIVITY HASTENS MINIMUM SUM-OF-DIAMETERS CLUSTERING

摘要

Dynamic data structures are presented for directed graphs that maintain (a) transitive closure and (b) decomposition into strongly connected components in a "semionline" situation with perfect deletion lookahead but no lookahead for insertions or queries. These algorithms give us "semionline" algorithms for dynamic 2-SAT, as a consequence of which the best known static algorithms for minimum sum-of-diameters clustering are improved by a O(log n) factor.