No label defined (Q3787478)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4050989
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4050989

      Statements

      0 references
      0 references
      0 references
      1988
      0 references
      union-find problem
      0 references
      set union problem
      0 references
      backtracking
      0 references
      data structure
      0 references
      space \(\times \,time\) complexity
      0 references
      [For the entire collection see Zbl 0635.00015.] We consider an extension of the well known set union problem, where backtracking over the union operations is possible. A data structure is presented which maintains a partition of an n-item set and performs each union in O(log log n) time, each find in O(log n) time and allows backtracking over the unions in O(1) time. The space complexity is O(n). The data structure favorably compares with other data structures proposed in the literature for such a problem also from the space \(\times time\) complexity point of view.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references