×

On DRC-covering of \(K_{n}\) by cycles. (English) Zbl 1031.05101

The authors consider a special case of the following problem. We have a given graph \(G\) that corresponds to a certain physical network and a logical graph \(I\) on the same set of vertices that represents the required connections on network \(G\). A covering of \(I\) is a family of subgraphs of \(I\) that cover all edges of \(I\), moreover any member of the family can be routed disjointly on \(G\). This latter, so-called disjoint routing constraint means that if \(I_k\) is a member of the covering family then for each edge \(uv\) of \(I_k\), there is a \(uv\) path in \(G\) such that all paths for \(I_k\) are vertex disjoint. The problem is to find a covering family of minimum size. The authors motivate this problem via survivable optical WDM networks and formulate both the directed and undirected problem. The special case considered in the paper is when the physical graph \(G\) is the cycle \(C_n\), the logical graph \(I\) is the complete graph \(K_n\) and the covering family consists only of cycles that are possibly of restricted size. The authors calculate the minimum size of a covering for several cases.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Communications dans les réseaux optiques par multiplexage en longueur d’onde, PhD thesis, Université de Nice Sophia-Antipolis, Janvier 2000.
[2] Cycles dans les graphes et G-configurations, Thèse d’Etat, Université de Paris Sud, Orsay, 1975.
[3] and A note on cycle covering. In: ACM Symposium on Parallel Algorithms and Architectures–SPAA, Crete, 4-6 July 2001.
[4] Bermond, Theor Comp Sci 233 pp 165– (2000)
[5] and Vertex disjoint routing of request cycles over a tori, In preparation.
[6] Graph decompositions and designs. In: and editors, Contemporary designs a collection of surveys. Wiley, 1992.
[7] and Decomposition into Cycles II: cycle systems. In: and editors, Contemporary designs a collection of surveys. Wiley, 1992.
[8] and Coverings and packings, In: and editors, Contemporary designs a collection of surveys, Wiley, 1992.
[9] Stanton, Ars combin 13 pp 61– (1982)
[10] Coverings. In: and editors, CRC handbook of combinatorial designs, chapter 8, CRC Press, 1996.
[11] Minimizing wavelengths in all-optical ring network. In the 7th International Symposium on Algorithms and Computation (ISAAC’96), volume 1178 of Lecture Notes in Computer Science, pages 346-355. Springer-Verlag, 1996.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.