Space-Efficient Message Routing inc-Decomposable Networks

DOI10.1137/0219011MaRDI QIDQ3474267zbMATH OpenOpenAlexFDO

Authors Greg N. Frederickson, Ravi Janardan

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

distributed networkgraph theoryk-outerplanar graphrouting messagesseparatorseries-parallel graphshortest paths

Mathematics Subject Classification ID

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

Recommendations

• Efficient Message Routing in Planar Networks
• Publication:4733694
• Improved routing strategies with succinct tables
• A trade-off between space and efficiency for routing tables
• scientific article; zbMATH DE number 3940741

Cited in

(20)

• Not all planar digraphs have small cycle separators
• Multidimensional interval routing schemes
• Graph theoretical issues in computer networks
• On devising Boolean Routing Schemes
• Interval routing in some planar networks.
• A survey on interval routing
• Compact routing messages in self-healing trees
• The compactness of adaptive routing tables
• An optimal message routing algorithm for double-loop networks
• Space-efficient and fault-tolerant message routing in outerplanar networks
• Efficient Message Routing in Planar Networks
• Proximity-preserving labeling schemes
• Compact and localized distributed data structures
• The Space Requirement of Local Forwarding on Acyclic Networks
• Interval routing schemes
• Representing graphs implicitly using almost optimal space
• Multi-dimensional Interval Routing Schemes
• On devising Boolean Routing schemes
• On multi-label linear interval routing schemes
• Topological routing schemes

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

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