Edge Finding Using the Theta-tree
Session date: 17 March 2025
Session host: Imko Marijnissen
Summary:
In this session, we will go back to the roots of algorithmics and investigate how algorithms have been improved using efficient data structures. We will use the case study of edge finding for the cumulative constraint as an example; in this work they develop a tree structure which allows efficient computation of certain information leading to an improved algorithm.
Relevant papers
-
Edge Finding Filtering Algorithm for Discrete Cumulative Resources in O(kn \log n)
Petr Vilím
In Principles and Practice of Constraint Programming - CP 2009, Mar 2009
This paper presents new Edge Finding algorithm for discrete cumulative resources, i.e. resources which can process several activities simultaneously up to some maximal capacity C. The algorithm has better time complexity than the current version of this algorithm: }{\backslashmathcal O}(kn {\backslashrm log} n)}versus }{\backslashmathcal O}(k n^2)}where n is number of activities on the resource and k is number of distinct capacity demands. Moreover the new algorithm is slightly stronger and it is able to handle optional activities. The algorithm is based on the Θ-tree – a binary tree data structure which already proved to be very useful in filtering algorithms for unary resource constraints.