Object location using path separators

DOI10.1145/1146381.1146411zbMath1314.68206OpenAlexW2150410057MaRDI QIDQ5177280

Cyril Gavoille, Ittai Abraham

Publication date: 10 March 2015

Published in: Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing (Search for Journal in Brave)

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

zbMATH Keywords

compact routingexcluded minorseparator

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22) Distributed algorithms (68W15)

Related Items (28)

Metric Embedding via Shortest Path Decompositions ⋮ Covering metric spaces by few trees ⋮ Prioritized Metric Structures and Embedding ⋮ Metric decompositions of path-separable graphs ⋮ Strong-diameter decompositions of minor free graphs ⋮ Reliable Spanners for Metric Spaces ⋮ Labelings vs. embeddings: on distributed and prioritized representations of distances ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ A note on exact distance labeling ⋮ Distributed computing of efficient routing schemes in generalized chordal graphs ⋮ Distance estimation and object location via rings of neighbors ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Polynomial bounds for centered colorings on proper minor-closed graph classes ⋮ Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Sparse covers for planar graphs and graphs that exclude a fixed minor ⋮ Recovering the long-range links in augmented graphs ⋮ Greedy routing in small-world networks with power-law degrees ⋮ Shortest-path queries in static networks ⋮ Transitive-Closure Spanners: A Survey ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Universal augmentation schemes for network navigability ⋮ Covering Metric Spaces by Few Trees ⋮ Greedy routing and the algorithmic small-world phenomenon ⋮ Distributed Computing of Efficient Routing Schemes in Generalized Chordal Graphs ⋮ On the Path Separability of Planar Graphs ⋮ On vertex rankings of graphs and its relatives ⋮ Fault-tolerant distance labeling for planar graphs

This page was built for publication: Object location using path separators