Efficient Union-Find for planar graphs and other sparse graph classes
From MaRDI portal
Publication:1274324
DOI10.1016/S0304-3975(97)00291-0zbMath0913.68084MaRDI QIDQ1274324
Publication date: 12 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items (5)
Optimal decremental connectivity in planar graphs ⋮ The longest common substring problem ⋮ Decremental SPQR-trees for Planar Graphs ⋮ Efficient region segmentation on compressed gray images using quadtree and shading representation ⋮ Contracting a Planar Graph Efficiently
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A class of algorithms which require nonlinear time to maintain disjoint sets
- Two linear time Union--Find strategies for image processing
- A linear-time algorithm for a special case of disjoint set union
- A complement to Tarjan's result about the lower bound on the complexity of the set union problem
- Lower bounds for the union-find and the split-find problem on pointer machines
- A Separator Theorem for Planar Graphs
- Efficiency of a Good But Not Linear Set Union Algorithm
- A general approach to connected-component labeling for arbitrary image representations
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
This page was built for publication: Efficient Union-Find for planar graphs and other sparse graph classes