Forwarding and optical indices of 4-regular circulant networks

DOI10.1016/J.JDA.2015.09.002MaRDI QIDQ891819zbMATH OpenOpenAlexFDO

Authors Heng-Soon Gan, Hamid Mokhtar, Sanming Zhou

Publication date 17 November 2015

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1405.6848

zbMATH Keywords

routing and wavelength assignmentcirculant networksedge-forwarding indexarc-forwarding indexoptical index

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Small world graphs, complex networks (graph-theoretic aspects) (05C82) Approximation algorithms (68W25) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38)

Abstract: 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 $pi(G,R)$. The edge-forwarding index $pi(G)$ is the minimum of $pi(G,R)$ over all possible all-to-all routings $R$, and the arc-forwarding index $overrightarrowpi(G)$ is defined similarly by taking direction into consideration, where an arc is an ordered pair of adjacent vertices. Denote by $w(G,R)$ 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 $w(G)$ is defined to be the minimum of $w(G,R)$ over all possible $R$, and the directed optical index $overrightarroww(G)$ 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 $pm1,pms$, $1<s<n/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.

Recommendations

• Forwarding and optical indices of a graph
• The forwarding index of the circulant networks
• The forwarding indices of graphs -- a survey
• The forwarding index of directed networks
• scientific article; zbMATH DE number 1034100

Cites work

• scientific article; zbMATH DE number 1262801 (Why is no real title available?)
• scientific article; zbMATH DE number 1054728 (Why is no real title available?)
• scientific article; zbMATH DE number 1421019 (Why is no real title available?)
• A 2-approximation algorithm for path coloring on a restricted class of trees of rings
• A complementary survey on double-loop networks
• A survey on Knödel graphs.
• A survey on multi-loop networks.
• All-to-all communication for some wavelength-routed all-optical networks
• All-to-all wavelength-routing in all-optical compound networks
• Colouring paths in directed symmetric trees with applications to WDM routing
• Computing the Diameter in Multiple-Loop Networks
• Efficient algorithms for wavelength assignment on trees of rings
• Efficient collective communciation in optical networks
• FROBENIUS CIRCULANT GRAPHS OF VALENCY FOUR
• Forwarding and optical indices of a graph
• Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes
• Gossiping and routing in undirected triple-loop networks
• LATIN 2004: Theoretical Informatics
• Multiplicative circulant networks. Topological properties and communication algorithms
• On forwarding indices of networks
• On orbital regular graphs and Frobenius graphs
• Optimal routing in double loop networks
• Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem
• The edge-forwarding index or orbital regular graphs
• The forwarding index of the circulant networks
• The forwarding indices of graphs -- a survey

Cited in

(7)

• Forwarding and optical indices of a graph
• A FEW FAMILIES OF CAYLEY GRAPHS AND THEIR EFFICIENCY AS COMMUNICATION NETWORKS
• Cube-connected circulants: bisection width, Wiener and forwarding indices
• The forwarding index of the circulant networks
• Algorithms and Computation
• The undirected optical indices of complete \(m\)-ary trees
• Recursive cubes of rings as models for interconnection networks

This page was built for publication: Forwarding and optical indices of 4-regular circulant networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q891819)