Skip to Main content Skip to Navigation
Conference papers

The master ring problem

Abstract : 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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184218
Contributor : Coordination Episciences Iam <>
Submitted on : Thursday, August 13, 2015 - 1:34:52 PM
Last modification on : Thursday, May 11, 2017 - 1:02:54 AM
Long-term archiving on: : Saturday, November 14, 2015 - 10:23:45 AM

File

dmAD0126.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01184218, version 1

Collections

Citation

Hadas Shachnai, Lisa Zhang. The master ring problem. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.287-296. ⟨hal-01184218⟩

Share

Metrics

Record views

76

Files downloads

650