Near-optimal fully-dynamic graph connectivity

No abstract is available for this paper.

• Publication year

  2000

• Venue

  Symposium on the Theory of Computing

• Publication date

  2000-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/335305.335345
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

  2001cited by this paper
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity

  1998influential reference
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms

  1997influential reference
• Decremental dynamic connectivity

  1997cited by this paper
• Sparsification—a technique for speeding up dynamic graph algorithms

  1997cited by this paper
• Lower Bounds for Fully Dynamic Connectivity Problems in Graphs

  1995influential reference
• Randomized dynamic graph algorithms with polylogarithmic time per operation

  1995cited by this paper
• Complexity Models for Incremental Computation

  1994cited by this paper
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications

  1985cited by this paper
• Data structures for on-line updating of minimum spanning trees

  1983cited by this paper
• A data structure for dynamic trees

  1981cited by this paper
• Efficiency of a Good But Not Linear Set Union Algorithm

  1972cited by this paper

• Constant-time Connectivity and 2-Edge Connectivity Querying in Dynamic Graphs

  2026cites this paper
• Fast and Compact Sketch-Based Dynamic Connectivity

  2025cites this paper
• Fully Dynamic Biconnectivity in Õ(log² n) Time

  2025cites this paper
• Dynamic Matroids: Base Packing and Covering

  2025cites this paper
• Towards Scalable and Practical Batch-Dynamic Connectivity (Abstract)

  2025cites this paper
• An Experimental Comparison of Tree-data Structures for Connectivity Queries on Fully-dynamic Undirected Graphs

  2025influential citation
• Identifying variants of molecules through database search of mass spectra

  2025cites this paper
• Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time

  2025cites this paper
• Fully-Adaptive Dynamic Connectivity of Square Intersection Graphs

  2024cites this paper
• Low-Latency Sliding Window Connectivity

  2024cites this paper
• Towards Scalable and Practical Batch-Dynamic Connectivity

  2024cites this paper
• Type-Based Verification of Connectivity Constraints in Lattice Surgery

  2024cites this paper
• Incremental Sliding Window Connectivity over Streaming Graphs

  2024cites this paper
• Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

  2024cites this paper
• Constant-time Connectivity Querying in Dynamic Graphs

  2024cites this paper
• Good r-divisions Imply Optimal Amortized Decremental Biconnectivity

  2024cites this paper
• Finding perfect matchings in bridgeless cubic multigraphs without dynamic (2-)connectivity

  2024cites this paper
• Listing the bonds of a graph in O˜(n)-delay

  2024cites this paper
• Splay top trees and 2-edge connectivity

  2023cites this paper
• The Graph Database Interface: Scaling Online Transactional and Analytical Graph Workloads to Hundreds of Thousands of Cores

  2023cites this paper
• Connectivity and Interference in Device-to-Device Networks in Poisson-Voronoi Cities

  2023cites this paper
• Certifying Fully Dynamic Algorithms for Recognition and Hamiltonicity of Threshold and Chain Graphs

  2023cites this paper
• High-Performance Graph Databases That Are Portable, Programmable, and Scale to Hundreds of Thousands of Cores

  2023cites this paper
• Achieving Sub-second Pairwise Query over Evolving Graphs

  2023cites this paper
• Worst-Case Deterministic Fully-Dynamic Biconnectivity in Changeable Planar Embeddings

  2023influential citation
• Splay Top Trees

  2022cites this paper
• All Your bases Are Belong to Us: Listing All Bases of a Matroid by Greedy Exchanges

  2022cites this paper
• Improved Dynamic Colouring of Sparse Graphs

  2022cites this paper
• Dynamic Spanning Trees for Connectivity Queries on Fully-dynamic Undirected Graphs

  2022cites this paper
• Dynamic Maxflow via Dynamic Interior Point Methods

  2022cites this paper
• New Lower Bounds and Upper Bounds for Listing Avoidable Vertices

  2022cites this paper
• Deterministic Fault-Tolerant Connectivity Labeling Scheme

  2022cites this paper
• Worst-case Deterministic Fully-Dynamic Planar 2-vertex Connectivity

  2022influential citation
• Tight dynamic problem lower bounds from generalized BMM and OMv

  2022cites this paper
• Neural Graph Databases

  2022cites this paper
• Research on anomaly detection method of nuclear power plant operation state based on unsupervised deep generative model

  2021cites this paper
• Dynamic Structural Clustering on Graphs

  2021cites this paper
• Dynamic Connectivity in Disk Graphs

  2021cites this paper
• Sampling from Potts on random graphs of unbounded degree via random-cluster dynamics

  2021cites this paper
• Determining 4-edge-connected components in linear time

  2021cites this paper
• Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness

  2021cites this paper
• A Scalable Concurrent Algorithm for Dynamic Connectivity

  2021cites this paper
• Sampling Hyperplanes and Revealing Disks ∗

  2021cites this paper
• DYNAMIC CONNECTIVITY: SOME GRAPHS OF INTEREST

  2021cites this paper
• Optimal Decremental Connectivity in Non-Sparse Graphs

  2021cites this paper
• Matching Theory Under Uncertainty

  2021cites this paper
• Fully Dynamic c-Edge Connectivity in Subpolynomial Time

  2020cites this paper
• Near-Optimal Algorithms for Reachability, Strongly-Connected Components and Shortest Paths in Partially Dynamic Digraphs

  2020cites this paper
• Approximating Multistage Matching Problems

  2020cites this paper
• VARIANTS OF THE DISCRETE FRÉCHET DISTANCE UNDER TRANSLATION∗

  2020influential citation
• Coarse-Grained Complexity for Dynamic Algorithms

  2020cites this paper
• A Novel and Efficient Link Discovery Mechanism in SDN

  2020cites this paper
• DYNAMIC CONNECTIVITY: THE STAR AND THE TREE STORY

  2020cites this paper
• Constant-Time Dynamic Weight Approximation for Minimum Spanning Forest

  2020cites this paper
• Deterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing

  2020cites this paper
• Connectedness matters: construction and exact random sampling of connected networks

  2020cites this paper
• Compatibility testing for rooted phylogenetic trees

  2020cites this paper
• Connectivity matters: Construction and exact random sampling of connected graphs

  2020cites this paper
• Dynamic Graph Algorithms and Graph Sparsification: New Techniques and Connections

  2019cites this paper
• Tree Compatibility, Incomplete Directed Perfect Phylogeny, and Dynamic Graph Connectivity: An Experimental Study

  2019cites this paper
• Three-in-a-tree in near linear time

  2019cites this paper
• A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

  2019cites this paper
• Rounding dynamic matchings against an adaptive adversary

  2019cites this paper
• Decremental strongly-connected components and single-source reachability in near-linear time

  2019cites this paper
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

  2019cites this paper
• Parallel Batch-Dynamic Graph Connectivity

  2019cites this paper
• On the König deficiency of zero-reducible graphs

  2019cites this paper
• Dynamic Disk Connectivity

  2019cites this paper
• Decremental SPQR-trees for Planar Graphs

  2018cites this paper
• Dynamic low-stretch trees via dynamic low-diameter decompositions

  2018cites this paper
• Guide to Graph Algorithms

  2018cites this paper
• Incremental Strong Connectivity and 2-Connectivity in Directed Graphs

  2018cites this paper
• Algebraic and Dynamic Graph Algorithms

  2018cites this paper
• A bounded-size clustering algorithm on fully-dynamic streaming graphs

  2018cites this paper
• On graph sample clustering

  2018cites this paper
• Batch-Parallel Euler Tour Trees

  2018cites this paper
• Nondeterminism and Completeness for Dynamic Algorithms

  2018cites this paper
• Dynamic algorithms: new worst-case and instance-optimal bounds via new connections

  2018cites this paper
• A new approach for the multiobjective minimum spanning tree

  2018cites this paper
• Good r-divisions Imply Optimal Amortised Decremental Biconnectivity

  2018cites this paper
• Cell-probe lower bounds from online communication complexity

  2017cites this paper
• Dynamic Bridge-Finding in Õ(log n) Amortized Time

  2017influential citation
• Solution of the sign problem in the Potts model at fixed fermion number

  2017cites this paper
• Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time

  2017cites this paper
• Offline Dynamic Higher Connectivity

  2017cites this paper
• Dynamic Bridge-Finding in $\tilde{O}(\log ^2 n)$ Amortized Time

  2017influential citation
• Big data algorithms beyond machine learning

  2017cites this paper
• Discovering recurring activity in temporal networks

  2017cites this paper
• An efficient algorithm for testing the compatibility of phylogenies with nested taxa

  2017cites this paper
• Space-Efficient Euler Partition and Bipartite Edge Coloring

  2017cites this paper
• Decremental single-source reachability in planar digraphs

  2017cites this paper
• Dynamic Parameterized Problems and Algorithms

  2017cites this paper
• A Practical Scalable Shared-Memory Parallel Algorithm for Computing Minimum Spanning Trees

  2017cites this paper
• Optimal Offline Dynamic 2, 3-Edge/Vertex Connectivity

  2017cites this paper
• Incrementalizing Abstract Interpretation

  2017cites this paper
• Incremental and Fully Dynamic Subgraph Connectivity For Emergency Planning

  2016influential citation
• Faster Randomized Worst-Case Update Time for Dynamic Subgraph Connectivity

  2016cites this paper
• Incremental 2-Edge-Connectivity in Directed Graphs

  2016cites this paper
• Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n1/2 - ε)-time

  2016cites this paper
• Large-Treewidth Graph Decompositions

  2016cites this paper