1994 · 40 citations · 22 references
ComputingComputer ScienceMathematicsAlgorithmsCombinatoricsData StructuresGraph AlgorithmsGraph TheoryBiconnected ComponentsConnected Components MaintenanceConnectivity AlgorithmsDynamic ConnectivityDynamic Graph AlgorithmsDynamic Graph Data StructuresFully Dynamic Graph Algorithms
We present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs and lower bounds for fully dynamic k-edge connectivity, k-vertex connectivity, and planarity testing. Fully dynamic algorithms maintain a graph during a sequence of insertions and deletions of edges or isolated vertices. Let m be the number of edges and n be the number of vertices in a graph. The time per operation of the best known algorithms are 0(@) in general graphs and O(log n) in plane graphs for fully dynamic connectivity and O(min{m2/3, n}) in general graphs and O(@)
22
Fast Algorithms for Finding Nearest Common Ancestors
Dov Harel, Robert E. Tarjan · SIAM Journal on Computing · 1984 · 1.1K citations