Complexity of the Forwarding Index Problem

DOI10.1137/0406033MaRDI QIDQ3136613zbMATH OpenOpenAlexFDO

Authors Rachid Saad

Publication date 14 October 1993

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0406033

zbMATH Keywords

forwarding indexnetworkNP-completenessrouting

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Forwarding indices of consistent routings and their complexity
• Upper bounds for the forwarding indices of communication networks
• Computation of the forwarding index via flows: A note
• On forwarding indices of networks
• The forwarding indices of graphs -- a survey

Cited in

(21)

• Forwarding and optical indices of a graph
• Forwarding index of cube-connected cycles
• The forwarding index of communication networks with given connectivity
• Static and dynamic low-congested interval routing schemes
• Forwarding indices of folded \(n\)-cubes
• Upper bounds for the forwarding indices of communication networks
• The forwarding index of directed networks
• Distance eigenvalues and forwarding indices of circulants
• Cube-connected circulants: bisection width, Wiener and forwarding indices
• On the restricted forwarding index problem in communication networks
• Metaheuristics for computing the forwarding index of a graph*
• Forwarding indices of consistent routings and their complexity
• Computation of the forwarding index via flows: A note
• Low-congested interval routing schemes for hypercubelike networks
• Lower bounds of forwarding indices of graph products
• Recursive cubes of rings as models for interconnection networks
• Algorithms and Computation
• Constructing integral uniform flows in symmetric networks with application to the edge-forwarding index problem
• Concurrent flows and packet routing in Cayley graphs (Preliminary version)
• Exact vertex forwarding index of the strong product of complete graph and cycle
• The forwarding indices of augmented cubes

This page was built for publication: Complexity of the Forwarding Index Problem

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