Hostname: page-component-78c5997874-8bhkd Total loading time: 0 Render date: 2024-11-16T09:20:25.537Z Has data issue: false hasContentIssue false
  • English
  • Français

Optimal union-find in Constraint Handling Rules

Published online by Cambridge University Press:  27 January 2006

TOM SCHRIJVERS  and
THOM FRÜHWIRTH
TOM SCHRIJVERS
Affiliation:
Department of Computer Science, K. U. Leuven, Belgium (e-mail: www.cs.kuleuven.ac.be/~toms/)
THOM FRÜHWIRTH
Affiliation:
Faculty of Computer Science, University of Ulm, Germany (e-mail: www.informatik.uni-ulm.de/pm/mitarbeiter/fruehwirth/)
Get access Rights & Permissions [Opens in a new window]

Abstract

Constraint Handling Rules (CHR) is a committed-choice rule-based language that was originally intended for writing constraint solvers. In this paper we show that it is also possible to write the classic union-find algorithm and variants in CHR. The programs neither compromise in declarativeness nor efficiency. We study the time complexity of our programs: they match the almost-linear complexity of the best known imperative implementations. This fact is illustrated with experimental results.

Keywords

declarative algorithmstime complexity analysisdisjoint-set problemunion-find algorithmconstraint handling rules
Type
Programming Pearl
Information
Theory and Practice of Logic Programming , Volume 6 , Issue 1-2 , January 2006 , pp. 213 - 224
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)