Forbidden-set distance labels for graphs of bounded doubling dimension

DOI10.1145/1835698.1835743zbMath1315.68196MaRDI QIDQ5176198

Ittai Abraham, Cyril Gavoille, Shiri Chechik, David Peleg

Publication date: 2 March 2015

Published in: Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1835698.1835743

zbMATH Keywords

fault-tolerance; compact routing; forbidden sets; doubling dimension; distance labeling

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R10: Graph theory (including graph drawing) in computer science

05C12: Distance in graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68M14: Distributed systems

68M15: Reliability, testing and fault tolerance of networks and computer systems

68M12: Network protocols

Related Items

The Traveling Salesman Problem: Low-Dimensionality Implies a Polynomial Time Approximation Scheme, Fault-Tolerant Compact Routing Schemes for General Graphs

Uses Software

• CCSTM

Cites Work

• Elastic Transactions
• Toward a theory of transactional contention managers
• Software transactional memory