3.7.75. DFS-bottleneck

A constraint for which a depth first search based procedure usually constitutes a bottleneck of its filtering algorithm. This is a pity, especially on dense graphsA common implementation trick relies on the fact that, quite often on dense graphs, a depth first search procedure develops one single path such that one can directly reach (i.e.Β with one single arc) the first node of the path from the last one (i.e.,Β we have one single strongly connected component). In this context the trick is to stop the depth first search procedure as soon as the last node of the path is reached, in order to avoid scanning through all remaining arcs of the graph. were most of the invocations to the filtering algorithm do not usually bring any new deductions. Motivated by this fact,Β randomized filtering algorithms were introduced inΒ [Katriel06] and in [KatrielVanHentenryck06] in the context of the πšπš•πš˜πš‹πšŠπš•_πšŒπšŠπš›πšπš’πš—πšŠπš•πš’πšπš’_πš•πš˜πš _πšžπš™ and the πšŠπš•πš•πšπš’πšπšπšŽπš›πšŽπš—πš constraints.