UDC 004.635, DOI: 10.2298/csis0902229L

On DRC-covering of λΚt(n) by cycles

Zhihe Liang1

  1. School of Mathematics and Information Science, Hebei Normal University
    Shijiazhuang 050016, P. R. China
    zhiheliang@163.com.cn

Abstract

This paper considers the cycle covering of complete multipartite graphs motivated by the design of survivable WDM networks, where the requests are routed on sub-networks which are protected independently from each other. The problem can be stated as follows: for a given graph G, find a cycle covering of the edge set of λΚt(n), where V(Kt(n))=V(G), such that each cycle in the covering satisfies the disjoint routing constraint (DRC). Here we consider the case where G=Ctn, a ring of size tn and we want to minimize the number of cycles ρ(nt, λ) in the covering. For the problem, we give the lower bound of ρ(nt, λ), and obtain the optimal solutions when n is even or n is odd and both λ and t are even.

Key words

Kt(n), DRC-covering, cycle, WDM network

Digital Object Identifier (DOI)

https://doi.org/10.2298/csis0902229L

Publication information

Volume 6, Issue 2 (December 2009)
Year of Publication: 2009
ISSN: 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Liang, Z.: On DRC-covering of λΚt(n) by cycles. Computer Science and Information Systems, Vol. 6, No. 2. (2009), https://doi.org/10.2298/csis0902229L