On a "double-edged" parallel implementation of a sort of dynamic programming for precedence constrained routing problems

We are going to present a yet another way of conducting dynamic programming for precedence constrained routing problems in parallel. The method is based on the "divide and conquer" strategy proposed in (Lawler, 1979) without proof of its validity. The idea of the method is to run both forward and backwards DP for the problem in parallel until the "middle" of the problem and then to "join" the obtained solutions. A proof of validity for the method will be presented.