About: Disjoint-set data structure

Facets (new session)
Description
Metadata
Settings
- Rule:
- Inverse Functional Properties:
- "Same As":

About: Disjoint-set data structure Goto Sponge NotDistinct Permalink

An Entity of Type : dbo:Building, within Data Space : el.dbpedia.org associated with source document(s)

In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets.

Attributes	Values
rdf:type	building
rdfs:label	Disjoint-set data structure (en)
rdfs:comment	In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets. (en)
sameAs	Disjoint-set data structure Disjoint-set data structure
dbp:wikiPageUsesTemplate	dbt:Anchor dbt:Annotated_link dbt:Em dbt:Math dbt:Mvar dbt:Reflist dbt:Data_structures dbt:Infobox_data_structure dbt:Math_proof
Subject	Amortized data structures Articles with example pseudocode Data structures Search algorithms
thumbnail	wiki-commons:Special:FilePath/Dsu_disjoint_sets_init.svg?width=300
foaf:depiction
gold:hypernym	Structure
prov:wasDerivedFrom	http://en.wikipedia.org/wiki/Disjoint-set_data_structure?oldid=1064010135&ns=0
Wikipage page ID	1037551 (xsd:integer)
page length (characters) of wiki page	30633 (xsd:nonNegativeInteger)
Wikipage revision ID	1064010135 (xsd:integer)
Link from a Wikipage to another Wikipage	Proof assistant Unification (computer science) Union (set theory) Ackermann function Amortized analysis Bernard Galler Boost (C++ libraries) Amortized data structures Articles with example pseudocode Data structures Search algorithms Jan van Leeuwen Davenport–Schinzel sequence Disjoint-set data structure Disjoint sets Jeffrey Ullman Kruskal's algorithm Robert Tarjan Component (graph theory) Computer science Coq Dynamic array John Hopcroft Michael Fredman Michael J. Fischer Michael Saks (mathematician) Minimum spanning tree Parent pointer tree Partition of a set Graph Persistent data structure Tree (graph theory) Iterated logarithm Register allocation dbr:Tracker_Component_Library
has abstract	In computer science, a disjoint-set data structure, also called a union–find data structure or merge–find set, is a data structure that stores a collection of disjoint (non-overlapping) sets. Equivalently, it stores a partition of a set into disjoint subsets. It provides operations for adding new sets, merging sets (replacing them by their union), and finding a representative member of a set. The last operation allows to find out efficiently if any two elements are in the same or different sets. While there are several ways of implementing disjoint-set data structures, in practice they are often identified with a particular implementation called a disjoint-set forest. This is a specialized type of forest which performs unions and finds in near constant amortized time. To perform a sequence of m addition, union, or find operations on a disjoint-set forest with n nodes requires total time O(mα(n)), where α(n) is the extremely slow-growing inverse Ackermann function. Disjoint-set forests do not guarantee this performance on a per-operation basis. Individual union and find operations can take longer than a constant times α(n) time, but each operation causes the disjoint-set forest to adjust itself so that successive operations are faster. Disjoint-set forests are both asymptotically optimal and practically efficient. Disjoint-set data structures play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph. The importance of minimum spanning trees means that disjoint-set data structures underlie a wide variety of algorithms. In addition, disjoint-set data structures also have applications to symbolic computation, as well in compilers, especially for register allocation problems. (en)
foaf:isPrimaryTopicOf	http://en.wikipedia.org/wiki/Disjoint-set_data_structure
is Wikipage redirect of	Proof of O(logn) time complexity of Union Find Proof of O(logn) time complexity of union-find Proof of O(log*n) time complexity of union–find Find union Path compression Mf set Mfset Disjoint-set forest Disjoint set (data structure) Disjoint set data structure Disjoint set forest Merge-Find-Set Merge-Find-set Merge-Find Set Merge-Find set Merge-find-set Merge-find data structure Merge-find set Union-Find Union-find Union-find algorithm Union-find data structure Union-find problem Union find Unionfind Union–find algorithm
is Link from a Wikipage to another Wikipage of	Ackermann function Biconnected component Big O notation

Faceted Search & Find service v1.17_git151 as of Feb 20 2025

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Nov 11 2024, on Linux (x86_64-ubuntu_focal-linux-gnu), Single-Server Edition (82 GB total memory, 2 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2025 OpenLink Software