## Abstract

This paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a "union tree") is known in advance. The algorithm executes an intermixed sequence of m union and find operations on n elements in O(m+n) time and O(n) space. This is a slight but theoretically significant improvement over the fastest known algorithm for the general problem, which runs in O(mα(m+n, n)+n) time and O(n) space, where a is a functional inverse of Ackermann's function. Used as a subroutine, the algorithm gives similar improvements in the efficiency of algorithms for solving several other problems, including two-processor scheduling, matching on convex graphs, finding nearest common ancestors off-line, testing a flow graph for reducibility, and finding two disjoint directed spanning trees. The algorithm obtains its efficiency by combining the fast algorithm for the general problem with table look-up on small sets, and requires a random access machine for its implementation. The algorithm extends to the case in which single-node additions to the union tree are allowed. The extended algorithm is useful in finding maximum cardinality matchings in nonbipartite graphs.

Original language | English (US) |
---|---|

Pages (from-to) | 209-221 |

Number of pages | 13 |

Journal | Journal of Computer and System Sciences |

Volume | 30 |

Issue number | 2 |

DOIs | |

State | Published - Apr 1985 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Computer Networks and Communications
- Computational Theory and Mathematics
- Applied Mathematics