### The master ring problem

*Hadas Shachnai, Lisa Zhang*

#### Abstract

We consider the

*master ring problem (MRP)*which often arises in optical network design. Given a network which consists of a collection of interconnected rings R1, …, RK, with n1, …, nK distinct nodes, respectively, we need to find an ordering of the nodes in the network that respects the ordering of every individual ring, if one exists. Our main result is an exact algorithm for MRP whose running time approaches Q·∏k=1K (nk/√2) for some polynomial Q, as the nk values become large. For the*ring clearance problem*, a special case of practical interest, our algorithm achieves this running time for rings of*any*size nk ≥2. This yields the first nontrivial improvement, by factor of (2√2)K ≈ (2.82)K, over the running time of the naive algorithm, which exhaustively enumerates all ∏k=1K (2nk) possible solutions.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page