Fault-Tolerant Compact Routing Schemes for General Graphs

DOI10.1007/978-3-642-22012-8_7MaRDI QIDQ3012912zbMATH OpenOpenAlexFDO

Authors Shiri Chechik

Publication date 7 July 2011

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22012-8_7

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Fault-tolerant compact routing schemes for general graphs
• Optimal fault-tolerant routings for connected graphs
• On fault tolerant routings in general networks
• Fault tolerant routings in complete multipartite graph
• Efficient fault-tolerant routings in networks
• Fault-Tolerant Fixed Routings in Some Families of Digraphs
• scientific article; zbMATH DE number 1696543
• Optimal fault-tolerant routings with small routing tables for k-connected graphs
• Fault-tolerant fixed routing in hypercube generalizations
• Efficient fault-tolerant fixed routings on \((k+1)\)-connected digraphs

Cites work

• \(f\)-sensitivity distance oracles and routing schemes
• A trade-off between space and efficiency for routing tables
• Approximate distance oracles
• Compact Forbidden-Set Routing
• Compact routing schemes with low stretch factor
• Compact routing with minimum stretch
• Computational geometry. Algorithms and applications.
• Connectivity oracles for failure prone graphs
• Distributed Computing: A Locality-Sensitive Approach
• Forbidden-set distance labels for graphs of bounded doubling dimension
• Improved routing strategies with succinct tables
• Memory requirement for universal routing schemes
• Optimal static range reporting in one dimension
• Space-efficiency for routing schemes of stretch factor three

Cited in

(9)

• Optimal fault-tolerant routings for connected graphs
• On reliable graphs with static routing plans
• Fault-tolerant compact routing schemes for general graphs
• Space efficient edge-fault tolerant routing
• Robust routing made easy
• A fault-tolerant routing scheme in dynamic networks
• Deterministic Fault-Tolerant Connectivity Labeling Scheme
• Deterministic fault-tolerant connectivity labeling scheme
• Fault-tolerant labeling and compact routing schemes

This page was built for publication: Fault-Tolerant Compact Routing Schemes for General Graphs

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