Forbidden-set distance labels for graphs of bounded doubling dimension. (English) Zbl 1315.68196
Proceedings of the 29th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, PODC ’10, Zurich, Switzerland, July 25–28, 2010. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-60558-888-9). 192-200 (2010).
MSC:
| 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) |
| 68M12 | Network protocols |
| 68M14 | Distributed systems |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
| 68Q25 | Analysis of algorithms and problem complexity |
Software:
CCSTMReferences:
| [1] | Ittai Abraham and Cyril Gavoille. Object location using path separators. In 25th ACM Symp. on Principles of Distributed Computing (PODC), 188-197, 2006. 10.1145/1146381.1146411 · Zbl 1314.68206 |
| [2] | Ittai Abraham, Cyril Gavoille, Andrew V. Goldberg, and Dahlia Malkhi. Routing in networks with low doubling dimension. In 26th Int. Conf. on Distributed Computing Systems (ICDCS), IEEE , 2006. 10.1109/ICDCS.2006.72 |
| [3] | Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In 41st ACM Symp. on Theory of Computing (STOC), 101-110, 2009. 10.1145/1536414.1536431 · Zbl 1304.68066 |
| [4] | Bruno Courcelle, Cyril Gavoille, Mamadou Mustapha Kanté, and David Andrew Twigg. Connectivity check in 3-connected planar graphs with obstacles. In Int. Conf. on Topological & Geometric Graph Theory, volume 31, 151-155. Electronic Notes in Discrete Mathematics, 2008. · Zbl 1267.05155 |
| [5] | Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. Unpublished manuscript, 2009. |
| [6] | Bruno Courcelle and David Andrew Twigg. Compact forbidden-set routing. In 24th Symp. on Theoretical Aspects of Computer Science (STACS), LNCS 4393, 37-48. SV, 2007. · Zbl 1186.68331 |
| [7] | Michael Dom. Compact routing. In Algorithms for Sensor and Ad Hoc Networks, LNCS 4621,187-202. SV, 2007. |
| [8] | Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In 20nd Symp. on Discrete Algorithms (SODA), 506-515. ACM-SIAM, 2009. · Zbl 1421.68121 |
| [9] | Camil Demetrescu and Mikkel Thorup. Oracles for distances avoiding a link-failure. In 13th Symp. on Discrete Algorithms (SODA), 838-843. ACM-SIAM, 2002. · Zbl 1093.68614 |
| [10] | Pierre Fraigniaud, Emmanuelle Lebhar, and Laurent Viennot. The inframetric model for the internet. In 27th IEEE Conf. on Computer Communications (INFOCOM), 1085-1093, 2008. |
| [11] | Anupam Gupta, Robert Krauthgamer, and James R. Lee. Bounded geometries, fractals, and low-distortion embeddings. In 44th IEEE Symp. on Foundations of Computer Science (FOCS), 534-543, IEEE, 2003. |
| [12] | Cyril Gavoille and David Peleg. Compact and localized distributed data structures. Distributed Computing, 16(2-3):111-120, 2003. 10.1007/s00446-002-0073-5 · Zbl 1448.68225 |
| [13] | Cyril Gavoille, David Peleg, Stéphane Pérennès, and Ran Raz. Distance labeling in graphs. J. Algorithms, 53(1):85-112, 2004. 10.1016/j.jalgor.2004.05.002 · Zbl 1068.68104 |
| [14] | Neelesh Khanna and Surender Baswana. Approximate shortest path oracle under vertex failure. In 26th Symp. on Theoretical Aspects of Computer Science (STACS), 2010. |
| [15] | Dmitri Krioukov, KC Claffy, Kevin Fall, and Arthur Brady. On compact routing for the internet. ACM SIGCOMM Computer Communication Review, 37(3):43-52, 2007. 10.1145/1273445.1273450 |
| [16] | Dmitri Krioukov, Kevin Fall, and Xiaowei Yang. Compact routing on internet-like graphs. In 23rd Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), volume 1, –219, 2004. |
| [17] | Goran Konjevod, Andréa Werneck Richa, and Donglin Xia. Optimal scale-free compact routing schemes in doubling networks. In 18th Symp. on Discrete Algorithms (SODA), 939-948. ACM-SIAM, 2007. · Zbl 1302.68017 |
| [18] | Goran Konjevod, Andréa Werneck Richa, and Donglin Xia. Dynamic routing and location services in metrics of low doubling dimension. In 22nd Int. Symp. on Distributed Computing (DISC), LNCS 5218, 379-393. SV, 2008. 10.1007/978-3-540-87779-0_26 · Zbl 1161.68343 |
| [19] | David Peleg. Proximity-preserving labeling schemes and their applications. In Proc. 25th Workshop on Graph- Theoretic Concepts in Computer Science, 30-41, 1999. · Zbl 0945.05053 |
| [20] | C. Greg Plaxton, Rajmohan Rajaraman, and Andréa Werneck Richa. Accessing nearby copies of replicated objects in a distributed environment. In 9th ACM Symp. on Parallel Algorithms and Architectures (SPAA), 311-320, 1997. 10.1145/258492.258523 |
| [21] | Mihai Pǎtraşcu and Mikkel Thorup. Planning for fast connectivity updates. In 48th IEEE Symp. on Foundations of Computer Science (FOCS), 263-271, IEEE, 2007. 10.1109/FOCS.2007.54 |
| [22] | Aleksandrs Slivkins. Distance estimation and object location via rings of neighbors. In 24th ACM Symp. on Principles of Distributed Computing (PODC), 41-50, 2005. 10.1145/1073814.1073823 · Zbl 1314.68032 |
| [23] | Aleksandrs Slivkins. Distance estimation and object location via rings of neighbors. Distributed Computing, 19(4):313-333, 2007. · Zbl 1266.68100 |
| [24] | Kunal Talwar. Bypassing the embedding: Algorithms for low dimensional metrics. In 36th ACM Symp. on Theory of Computing (STOC), 281-290, 2004. 10.1145/1007352.1007399 · Zbl 1192.68918 |
| [25] | Mikkel Thorup. Compact oracles for reachability and approximate distances in planar digraphs. J. ACM, 51(6):993-1024, 2004. 10.1145/1039488.1039493 · Zbl 1125.68394 |
| [26] | David Andrew Twigg. Forbidden-set Routing. PhD thesis, University of Cambridge (King’s College), 2006. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
