Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > SHARP Framework

Tools: Print

SHARP - A Smart Hypertree decomposition-based Algorithm fRamework for Parameterized problems



Release of SHARP 1.1.1


Version 1.1.1 of SHARP is now available (see Downloads). It features a new normalization option (weak normalization) and optionally adds an empty root or empty leaves to the decomposition.


Release of SHARP 1.1


Version 1.1 of SHARP is now available (see Downloads). It includes some bugfixes and functions for greater convenience.


Release of SHARP 1.0


SHARP has hit stable and has now been released as version 1.0 (see Downloads)



SHARP is a framework that enables rapid development of algorithms that are based on tree or hypertree decompositions. Classically, such algorithms perform a bottom-up evaluation of the (hyper-)tree, where at each node the possible partial solutions are calculated, and at the root node, one arrives at the actual solution to the original problem. If the (hyper-)tree decomposition is normalized, there are only four different node types and thus only four basic operations for each node type have to be implemented. The framework provides (hyper-)tree decomposition routines and algorithm interfaces that only require the implementation of the four aforementioned operations plus input parsing in order to get a running algorithm. All object and data management that is required to e.g. traverse the tree is handled by the framework using algorithm-independent code.

The documentation for the framework is available here.



The SHARP source code is available under the open-source GPLv3 license. Run the usual ./configure && make && sudo make install to compile and install.

In order to compile the library, the GNU Multiple Precision Arithmetic Library (GMP - available here) should be available on your system. If you want to compile the code without this, you can add the --without-gmp option when calling the ./configure script. In this case, the GMP library is not needed, however only 64bit integers are used for counting, as opposed to arbitrary precision integers.



The SHARP library is currently being used in the following projects that we know of:

Note that the above list may be and probably is incomplete.

Last updated: 2011-05-30 14:44

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung