Discrete Mathematics & Theoretical Computer Science |

3383

- 1 Department of Computer Science [Haifa]
- 2 Alcatel-Lucent Bell Labs

We consider the $\textit{master ring problem (MRP)}$ which often arises in optical network design. Given a network which consists of a collection of interconnected rings $R_1, \ldots, R_K$, with $n_1, \ldots, 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. Our main result is an exact algorithm for MRP whose running time approaches $Q \cdot \prod_{k=1}^K (n_k/ \sqrt{2})$ for some polynomial $Q$, as the $n_k$ values become large. For the $\textit{ring clearance problem}$, a special case of practical interest, our algorithm achieves this running time for rings of $\textit{any}$ size $n_k \geq 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 $\prod_{k=1}^K (2n_k)$ possible solutions.

Source: HAL:hal-01184218v1

Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: Master ring,shortest common supersequence,optical networks,exact algorithms,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]

This page has been seen 135 times.

This article's PDF has been downloaded 259 times.