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

DOI10.1016/S0304-3975(97)00291-0MaRDI QIDQ1274324zbMATH OpenFDO

Authors Jens Gustedt

Publication date 12 January 1999

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

Full work available at URL https://doi.org/10.1016/S0304-3975(97)00291-0

zbMATH Keywords

graph algorithmsimage segmentationplanar graphsunion-find

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)

Recommendations

• Two linear time Union--Find strategies for image processing
• Memory management for union-find algorithms
• A simple and efficient union-find-delete algorithm
• The recognition of union trees

Cites work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• A complement to Tarjan's result about the lower bound on the complexity of the set union problem
• A general approach to connected-component labeling for arbitrary image representations
• A linear-time algorithm for a special case of disjoint set union
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A Separator Theorem for Planar Graphs
• Efficiency of a Good But Not Linear Set Union Algorithm
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 53772 (Why is no real title available?)
• scientific article; zbMATH DE number 566078 (Why is no real title available?)
• scientific article; zbMATH DE number 1142295 (Why is no real title available?)
• Lower bounds for the union-find and the split-find problem on pointer machines
• Two linear time Union--Find strategies for image processing

Cited in

(12)

• Recognizing union-find trees is NP-complete
• Optimal decremental connectivity in planar graphs
• Efficient region segmentation on compressed gray images using quadtree and shading representation
• The longest common substring problem
• Decremental SPQR-trees for Planar Graphs
• Memory management for union-find algorithms
• Contracting a planar graph efficiently
• Recognizing union-find trees is NP-complete, even without rank info
• Efficient union-find for planar graphs and other sparse graph classes (extended abstract)
• Good \(r\)-divisions imply optimal amortized decremental biconnectivity
• Two linear time Union--Find strategies for image processing
• Good r-divisions imply optimal amortized decremental biconnectivity

This page was built for publication: Efficient Union-Find for planar graphs and other sparse graph classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1274324)