Optimal Groomings with Grooming Ratios Six and Seven


Creative Commons License

Ge G., Kolotoğlu E., Wei H.

JOURNAL OF COMBINATORIAL DESIGNS, cilt.23, ss.400-415, 2015 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 23
  • Basım Tarihi: 2015
  • Doi Numarası: 10.1002/jcd.21428
  • Dergi Adı: JOURNAL OF COMBINATORIAL DESIGNS
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.400-415
  • Yıldız Teknik Üniversitesi Adresli: Evet

Özet

Grooming uniform all-to-all traffic in optical (SONET) rings with grooming ratio C requires the determination of a decomposition of the complete graph into subgraphs each having at most C edges. The drop cost of such a grooming is the total number of vertices of nonzero degree in these subgraphs, and the grooming is optimal when the drop cost is minimum. The determination of optimal C-groomings has been considered for 3C9, and completely solved for 3C5. For C=6, it has been shown that the lower bound for the drop cost of an optimal C-grooming can be attained for almost all orders with 5 exceptions and 308 possible exceptions. For C=7, there are infinitely many unsettled orders; especially the case n2 is far from complete. In this paper, we show that the lower bound for the drop cost of a 6-grooming can be attained for almost all orders by reducing the 308 possible exceptions to 3, and that the lower bound for the drop cost of a 7-grooming can be attained for almost all orders with seven exceptions and 16 possible exceptions. Moreover, for the unsettled orders, we give upper bounds for the minimum drop costs.