Simultaneous Disjoint Routing in Regular Graphs

Given a graph G = (V,E) and k pairs of vertices (s1,t1),(s2,t2),…, (sk,tk), we have to find minimum cost routes between each si and ti where 1 ≤ i ≤ k, satisfying either of the following two disjointness conditions : vertex disjointness (no two routes share any vertex) and arc disjointness (no two routes share any edge). For special structured graphs, a divide and conquer strategy comes up with a fast solution or provides a decomposition tree to backtrack when splitting fails. Each division step amounts to solve a non linear assignment problem with side constraints whose degree is given by the number of hops allowed in a division. 2D meshes (square or hexagonal) along with Cayley graphs are studied under a maximum number of 2 hops.