Forwarding and optical indices of 4-regular circulant networks

详细信息    查看全文

• 作者：Heng-Soon Gan ^{hsg@unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Hamid Mokhtar ; ^{hmokhtar@student.unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author} ; Sanming Zhou ^{smzhou@ms.unimelb.edu.au" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Circulant networks ; Arc-forwarding index ; Edge-forwarding index ; Optical index ; Routing and wavelength assignment
• 刊名：Journal of Discrete Algorithms
• 出版年：2015
• 出版时间：November 2015
• 年：2015
• 卷：35
• 期：Complete
• 页码：27-39
• 全文大小：428 K

文摘

An all-to-all routing in a graph G is a set of oriented paths of G, with exactly one path for each ordered pair of vertices. The load of an edge under an all-to-all routing R is the number of times it is used (in either direction) by paths of R  , and the maximum load of an edge is denoted by lsi1" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si1.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=64025d94fa974fb16534812a19020997" title="Click to view the MathML source">π(G,R)lass="mathContainer hidden">lass="mathCode">low="scroll">πlse">(G,Rlse">). The edge-forwarding index lsi2" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si2.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=371030956d94d6cd3e5d232f3268f06b" title="Click to view the MathML source">π(G)lass="mathContainer hidden">lass="mathCode">low="scroll">πlse">(Glse">) is the minimum of lsi1" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si1.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=64025d94fa974fb16534812a19020997" title="Click to view the MathML source">π(G,R)lass="mathContainer hidden">lass="mathCode">low="scroll">πlse">(G,Rlse">) over all possible all-to-all routings R  , and the arc-forwarding index lsi3" class="mathmlsrc">le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si3.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=12e675ddd0e7ad2cd30d7e80d6a97d73">lass="imgLazyJSB inlineImage" height="15" width="33" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S157086671500101X-si3.gif">lass="mathContainer hidden">lass="mathCode">low="scroll">πlse">→lse">(Glse">) is defined similarly by taking direction into consideration, where an arc is an ordered pair of adjacent vertices. Denote by lsi4" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si4.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=79881cd0314920ca3cfa151d44681a69" title="Click to view the MathML source">w(G,R)lass="mathContainer hidden">lass="mathCode">low="scroll">wlse">(G,Rlse">) the minimum number of colours required to colour the paths of R   such that any two paths having an edge in common receive distinct colours. The optical index lsi5" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si5.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=89eb1b8d0a9e8cfcc97aa316a068a826" title="Click to view the MathML source">w(G)lass="mathContainer hidden">lass="mathCode">low="scroll">wlse">(Glse">) is defined to be the minimum of lsi4" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si4.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=79881cd0314920ca3cfa151d44681a69" title="Click to view the MathML source">w(G,R)lass="mathContainer hidden">lass="mathCode">low="scroll">wlse">(G,Rlse">) over all possible R  , and the directed optical index lsi6" class="mathmlsrc">le="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si6.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=7b4316b04fa896729445b1c7ec1b5278">lass="imgLazyJSB inlineImage" height="16" width="33" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S157086671500101X-si6.gif">lass="mathContainer hidden">lass="mathCode">low="scroll">wlse">→lse">(Glse">) is defined similarly by requiring that any two paths having an arc in common receive distinct colours. In this paper we obtain lower and upper bounds on these four invariants for 4-regular circulant graphs with connection set lsi7" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si7.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=2a63088defeb74d9406dfa46b8317248" title="Click to view the MathML source">{±1,±s}lass="mathContainer hidden">lass="mathCode">low="scroll">lse">{±1,±slse">}, lsi8" class="mathmlsrc">lass="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S157086671500101X&_mathId=si8.gif&_user=111111111&_pii=S157086671500101X&_rdoc=1&_issn=15708667&md5=0dd6919caeedbda5469eedbdc0a496dd" title="Click to view the MathML source">1<s<n/2lass="mathContainer hidden">lass="mathCode">low="scroll">1<s<nlse">/2. We give approximation algorithms with performance ratio a small constant for the corresponding forwarding index and routing and wavelength assignment problems for some families of 4-regular circulant graphs.