Figure 7

The incorporation of cavity matching subroutines in the DP algorithm. (a) Upon reaching the entry corresponding to$T_u^{v_1}$ and$S_{u^{\prime }}^{v_2^{\prime }}$, all values of the form${\mathit{\text{Rooted-HSA}}}^{-r}(T_{v_j}^u,S_{v_{j^{\prime }}^{\prime }}^{u^{\prime }})$ for v _j  ∈ N(u) ∖ {v₁} and$v_{j^{\prime }}^{\prime }\in N\left(u^{\prime }\right)$ are computed (see (b)). This allows to compute all values$\mathit{\text{MCM}}\left(N\right(u)\setminus \{v_1\},N(u^{\prime })\setminus \{v_j^{\prime }\},w_{u,u^{\prime }}^{v_1,v_j^{\prime }})$, by solving the All-Cavity-MCM problem over the instance$\left(N\right(u)\setminus \{v_1\},N(u^{\prime }),w_{u,u^{\prime }}^{v_1})$, and thus computing term III with respect to all remaining entries in the first row of$H_{u,u^{\prime }}$. (c) Upon reaching the entry corresponding to$T_u^{v_2}$ and$S_{u^{\prime }}^{v_2^{\prime }}$, all values of the form${\mathit{\text{Rooted-HSA}}}^{-r}(T_{v_j}^u,S_{v_{j^{\prime }}^{\prime }}^{u^{\prime }})$ for v _j  ∈ N(u) and$v_{j^{\prime }}^{\prime }\in N\left(u^{\prime }\right)$ are computed (see (d)). This allows to compute all values$\mathit{\text{MCM}}\left(N\right(u)\setminus \{v_j\},N(u^{\prime })\setminus \{v_{j^{\prime }}^{\prime }\},w_{u,u^{\prime }}^{v_j,v_{j^{\prime }}^{\prime }})$, by solving the All-Pairs-Cavity-MCM problem over the instance$\left(N\right(u),N(u^{\prime }),w_{u,u^{\prime }})$, and thus computing term III with respect to all remaining entries in$H_{u,u^{\prime }}$.