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.
Type de document :
Communication dans un congrès
Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.287-296, 2005, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01184218
Contributeur : Coordination Episciences Iam <>
Soumis le : jeudi 13 août 2015 - 13:34:52
Dernière modification le : jeudi 11 mai 2017 - 01:02:54
Document(s) archivé(s) le : samedi 14 novembre 2015 - 10:23:45

Fichier

dmAD0126.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01184218, version 1

Collections

Citation

Hadas Shachnai, Lisa Zhang. The master ring problem. Conrado Martìnez. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, pp.287-296, 2005, DMTCS Proceedings. 〈hal-01184218〉

Partager

Métriques

Consultations de la notice

54

Téléchargements de fichiers

177