Jean-François Baget, Sébastien Laborie, Bi-intervals for backtracking on temporal constraint networks, in: Proc. 14th international conference on temporal representation and reasoning (TIME), Alicante (SP), (Valentin Goranko, Sean Wang (eds), Proc. 14th international conference on temporal representation and reasoning (TIME), Alicante (SP), IEEE Computer society, Los Alamitos (CA), 2007), pp163-168, 2007
Checking satisfiability of temporal constraint networks involves infinite variables domains. We explore a solution based upon finite partitions of infinite domains. Though a straightforward partition results in a sound and complete backtrack, its extension to forward checking is not complete. Using bi-intervals, we obtain sound and complete backtrack and forward checking algorithms. Moreover, we show that bi-intervals used in a hybrid algorithm which also instantiates constraints improve backtrack efficiency.