2004/01/01 by Sarnath Ramnath · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Data Management and Algorithms #Digraph #Transitive closure #Combinatorics #Mathematics #Cluster analysis #Transitive relation #Closure (psychology) #Discrete mathematics #Decomposition #Transitive reduction #Directed graph #Algorithm #Graph
paper · doi:10.1137/s0895480102396099
openalex publication_date 2004/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
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.