We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
from Part III - CHR programs and applications
Published online by Cambridge University Press: 10 February 2010
The classical union-find (also: disjoint set union) (UF) algorithm was introduced by Tarjan in the 1970s. This essential algorithm efficiently solves the problem of maintaining a collection of disjoint sets under the operation of union. It is the basis for many graph algorithms (e.g. efficient computation of spanning trees). By definition of set operations, a union operator working on representatives of sets is an equivalence relation, i.e. we can view sets as equivalence classes and deal with equality.
We give concise CHR programs for the union-find algorithm and some variants that have best-known time and space complexity. This is believed impossible in other pure declarative programming languages due to their lack of destructive assignment which is needed for efficient update of graph data structures. Our program benefits from the guaranteed properties of wellbehaved CHR programs such as the anytime and online algorithm property. This makes our implementation particularly well-suited for use in constraint solvers.
Using CHR analysis techniques we study logical correctness and confluence of these programs. We observe the essential update of the algorithm which makes it nonconfluent and nonmonotonic but efficient. Based on the confluence analysis, we are able to parallelize the UF algorithm. This is considered to be hard in the literature. When the UF algorithm is extended to deal with function terms (rational trees), the algorithm can be used for optimal complexity unification. Last but not least, we discuss a generalization of UF that yields novel algorithms for simple Boolean and linear equations that are well-suited for constraint solving.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
