Efficient union-find for planar graphs and other sparse graph classes
- 6 August 1998
- journal article
- Published by Elsevier in Theoretical Computer Science
- Vol. 203 (1) , 123-141
- https://doi.org/10.1016/s0304-3975(97)00291-0
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small TreewidthSIAM Journal on Computing, 1996
- Lower Bounds for the Union–Find and the Split–Find Problem on Pointer MachinesJournal of Computer and System Sciences, 1996
- Two linear time Union-Find strategies for image processingTheoretical Computer Science, 1996
- A general approach to connected-component labeling for arbitrary image representationsJournal of the ACM, 1992
- A linear-time algorithm for a special case of disjoint set unionJournal of Computer and System Sciences, 1985
- A complement to Tarjan's result about the lower bound on the complexity of the set union problemInformation Processing Letters, 1980
- A Separator Theorem for Planar GraphsSIAM Journal on Applied Mathematics, 1979
- A class of algorithms which require nonlinear time to maintain disjoint setsJournal of Computer and System Sciences, 1979
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975