Efficient Union-Find for planar graphs and other sparse graph classes

DOI10.1016/S0304-3975(97)00291-0zbMath0913.68084MaRDI QIDQ1274324

Jens Gustedt

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

planar graphsgraph algorithmsimage segmentationunion-find

Mathematics Subject Classification ID

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