Exact algorithms for the master ring problem

✍ Scribed by Hadas Shachnai; Lisa Zhang; Tomomi Matsui

• Publisher: John Wiley and Sons
• Year: 2008
• Tongue: English
• Weight: 188 KB
• Volume: 52
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.20226

✦ Synopsis

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 R~1~,…,R~K~, with n~1~,…,n~K~ 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. We show that MRP is NP‐complete, and therefore, it is unlikely to be solvable by a polynomial time algorithm. Our main result is an algorithm which solves MRP in $ Q \cdot \Pi_{k=1}^{K} (n_{k}/\sqrt{2}) $ steps, for some polynomial Q, as the n~k~ 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 n~k~ ≥ 2. This yields the first nontrivial improvement, by factor of $ (2\sqrt{2})^{K} \approx (2.82)^{K} $, over the running time of the naive algorithm, which exhaustively enumerates all $ \Pi_{k=1}^{K} (2n_{k}) $ possible solutions. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008