O(n log n) Filtering Algorithms for Unary Resource Constraint

摘要

So far, edge-finding is the only one major filtering algorithm for unary resource constraint with time complexity O(n log n). This paper proposes O(n log n) versions of another two filtering algorithms: not-firstot-last and propagation of detectable precedences. These two algorithms can be used together with the edge-finding to further improve the filtering. This paper also propose new O(n log n) implementation of fail detection (overload checking).