Content deleted Content added
Rlucas stats (talk | contribs) |
m citation for novel deletion-friendly union-find impls does not have a page number; i will try to fix this presently, if i can locate it |
||
Line 250:
This data structure is used by the [[Boost Graph Library]] to implement its [http://www.boost.org/libs/graph/doc/incremental_components.html Incremental Connected Components] functionality. It is also a key component in implementing [[Kruskal's algorithm]] to find the [[minimum spanning tree]] of a graph.
Note that the regular implementation as disjoint-set forests does not allow the deletion of edges, even without path compression or the rank heuristic. However, there exist modern implementations that allow for constant-time deletion.<ref>{{Cite book |url=https://www.worldcat.org/oclc/262681795 |title=Automata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings |date=2005 |publisher=Springer |others=Luís. Caires, European Association for Theoretical Computer Science |isbn=978-3-540-31691-6 |___location=Berlin |oclc=262681795}}</ref>{{vague citation|date=May 2023}}
Sharir and Agarwal report connections between the worst-case behavior of disjoint-sets and the length of [[Davenport–Schinzel sequence|Davenport–Schinzel sequences]], a combinatorial structure from computational geometry.<ref name="Sharir1995">{{cite book|first1=M.|last1=Sharir|first2=P.|last2=Agarwal|title=Davenport-Schinzel sequences and their geometric applications|title-link= Davenport–Schinzel Sequences and Their Geometric Applications|publisher=Cambridge University Press|year=1995}}</ref>
| |||