[gecode-users] edge-finder propagator

[Jan Kelbel]

Hi Filip,

thank you for the information.
The implementation of the O(n^2) edge-finder of [Baptiste,Le Pape, 
Nuijten] seemed to us easier to implement than the O(n log n) algorithm 
of Vilim, which uses binary trees.
So we chose the O(n^2), as it was the first propagator we were implementing.

Maybe we should try to implement that O(n log n) version.

Cheers
Jan

Filip Konvička napsal(a):
> 
> 
> Hi Jan,
> 
>> thank you for the reply. I forgot to mention that we are implementing 
>> disjunctive edge-finder.
> 
> at
> 
>    http://kti.mff.cuni.cz/~vilim/
> 
> you'll find some interesting papers, one of which is
> 
>   "O(n log n) Filtering Algorithms for Unary Resource Constraint"
>   http://kti.mff.cuni.cz/~vilim/nlogn.pdf
> 
> That's pretty easy to implement. You can also derive a branching for 
> first/lasts quite easily from that.
> 
> Hope this helps,
> Filip
>