Space-Efficient Message Routing inc-Decomposable Networks

DOI10.1137/0219011zbMath0696.68022OpenAlexW2049706063MaRDI QIDQ3474267

Ravi Janardan, Greg N. Frederickson

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1532&context=cstech

zbMATH Keywords

graph theoryshortest pathsseries-parallel graphseparatordistributed networkrouting messagesk-outerplanar graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Applications of graph theory to circuits and networks (94C15) Theory of operating systems (68N25) Theory of software (68N99) Algorithms in computer science (68W99)

Related Items (13)

An optimal message routing algorithm for double-loop networks ⋮ Proximity-preserving labeling schemes ⋮ Multi-dimensional Interval Routing Schemes ⋮ Interval routing in some planar networks. ⋮ On multi-label linear interval routing schemes ⋮ Compact and localized distributed data structures ⋮ Not all planar digraphs have small cycle separators ⋮ Representing graphs implicitly using almost optimal space ⋮ Interval routing schemes ⋮ Multidimensional interval routing schemes ⋮ The compactness of adaptive routing tables ⋮ A survey on interval routing ⋮ Graph theoretical issues in computer networks

This page was built for publication: Space-Efficient Message Routing inc-Decomposable Networks