Worst-case and amortised optimality in union-find (extended abstract)

No abstract is available for this paper.

• Publication year

  1999

• Venue

  Symposium on the Theory of Computing

• Publication date

  1999-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/301250.301383
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sorting and Searching

  2012cited by this paper
• A Generalization of a Lower Bound Technique due to Fredman and Saks

  2001cited by this paper
• Marked ancestor problems

  1998cited by this paper
• Lower Bounds for the Union-Find and the Sp;it-Find Problem on Pointer Machines

  1996cited by this paper
• What is a “pointer machine”?

  1995cited by this paper
• Data structures and algorithms for disjoint set union problems

  1991cited by this paper
• New techniques for the union-find problem

  1990cited by this paper
• Data structures for weighted matching and nearest common ancestors with linking

  1990cited by this paper
• The cell probe complexity of dynamic data structures

  1989cited by this paper
• A scaling algorithm for weighted matching on general graphs

  1985cited by this paper
• On the Single-Operation Worst-Case Time Complexity on the Disjoint Set Union Problem

  1985cited by this paper
• Worst-case Analysis of Set Union Algorithms

  1984cited by this paper
• Should Tables Be Sorted?

  1981cited by this paper
• A Complement to Tarjan's Result about the Lower Bound on the Complexity of the Set Union Problem

  1980cited by this paper
• On the Power of Random Access Machines

  1979cited by this paper
• A Class of Algorithms which Require Nonlinear Time to Maintain Disjoint Sets

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

  1972cited by this paper

• Connected components labeling based on union-find operations applied to connected branches

  2017cites this paper
• On the Succinct Representation of Equivalence Classes

  2017cites this paper
• Simplified Data Structure Lower Bounds for Dynamic Graph Connectivity

  2017cites this paper
• New Randomized Data Structure Lower Bounds for Dynamic Graph Connectivity

  2016cites this paper
• Succinct Data Structures for Representing Equivalence Classes

  2013cites this paper
• Fast Constructions of Lightweight Spanners for General Graphs

  2012cites this paper
• Fast Constructions of Light-Weight Spanners for General Graphs

  2012cites this paper
• Don't rush into a union: take time to find your roots

  2011cites this paper
• Unifying the Landscape of Cell-Probe Lower Bounds

  2010cites this paper
• Lower bound techniques for data structures

  2008cites this paper
• (Data) STRUCTURES

  2008cites this paper
• Two Strategies to Speed up Connected Component Labeling Algorithms

  2005cites this paper
• Optimizing connected component labeling algorithms

  2005cites this paper
• Union-Find with Constant Time Deletions

  2005cites this paper
• Two Strategies to Speed up Connected Component Labeling Algorithms

  2005cites this paper
• Implementing and Analysing Union-Find in CHR

  2004cites this paper
• Nearest Common Ancestors: A Survey and a New Algorithm for a Distributed Environment

  2004cites this paper
• Meldable heaps and boolean union-find

  2002cites this paper
• A Generalization of a Lower Bound Technique due to Fredman and Saks

  2001cites this paper
• Improved Algorithms for Finding Level Ancestors in Dynamic Trees

  2000cites this paper
• Cell probe complexity-a survey

  1999influential citation