TU Berlin

Combinatorial Optimization & Graph Algorithms group (COGA)1996

COGA 5-Wheel

Page Content

to Navigation

Preprints 1996

Two Linear Time Union-Find Strategies for Image Processing
Citation key Report-375-1994
Author Christophe Fiorio and Jens Gustedt
Year 1994
Number 375
Note Appeared in Theoretical Computer Science, vol. 154, no. 2, 1996.
Institution Technische Universität Berlin, Institut für Mathematik
Abstract We consider \UF\ as an appropriate data structure to obtain two linear time algorithms for the segmentation of images. The linearity is obtained by restricting the order in which \Union's are performed. For one algorithm the complexity bound is proven by amortizing the \Find\ operations. For the other we use periodic updates to keep the relevant part of our \UF-tree of constant height. Both algorithms are generalized and lead to new linear strategies for \UF\ that are neither covered by the algorithm of Gabow and Tarjan nor by the one of Dillencourt et al.
Bibtex Type of Publication Preprint
Link to publication Download Bibtex entry

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe