Forwarding and optical indices of 4-regular circulant networks

DOI10.1016/J.JDA.2015.09.002zbMATH Open1343.05141arXiv1405.6848OpenAlexW3101700496MaRDI QIDQ891819FDOQ891819

Authors: Heng-Soon Gan, Hamid Mokhtar, Sanming Zhou 

Publication date: 17 November 2015

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

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.

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

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

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)

Cites Work

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

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)