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

networkNP-completenessroutingforwarding index

Mathematics Subject Classification ID

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

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

(20)

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

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)