Distance labeling in graphs
From MaRDI portal
Publication:4826764
DOI10.1016/j.jalgor.2004.05.002zbMath1068.68104MaRDI QIDQ4826764
Stéphane Pérennes, Cyril Gavoille, Ran Raz, David Peleg
Publication date: 12 November 2004
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.05.002
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C78: Graph labelling (graceful graphs, bandwidth, etc.)
Related Items
Adjacency Labeling Schemes and Induced-Universal Graphs, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Isometric Universal Graphs, Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension, Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs, Shortest-path queries in static networks, ReHub, Inductive computations on graphs defined by clique-width expressions, Distributed Relationship Schemes for Trees, Short labeling schemes for topology recognition in wireless tree networks, Fault-tolerant distance labeling for planar graphs, Distributed algorithms for ultrasparse spanners and linear size skeletons, Fault-tolerant distance labeling for planar graphs, Better distance labeling for unweighted planar graphs, The hierarchical hub labeling is non-efficient, Topology recognition with advice, Drawing maps with advice, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, Efficient distributed computation of distance sketches in networks, Decomposing a graph into shortest paths with bounded eccentricity, Better distance labeling for unweighted planar graphs, Fast rendezvous with advice, Fast deterministic distributed algorithms for sparse spanners, A note on models for graph representations, Localized and compact data-structure for comparability graphs, Bimagic vertex labelings, Impact of knowledge on election time in anonymous networks, A note on exact distance labeling, Distance estimation and object location via rings of neighbors, General compact labeling schemes for dynamic trees, Constrained-path labellings on graphs of bounded clique-width, Randomized proof-labeling schemes, Advice complexity of treasure hunt in geometric terrains, Optimal centrality computations within bounded clique-width graphs, Distance labeling schemes for \(K_4\)-free bridged graphs, An efficient noisy binary search in graphs via Median approximation, Eccentricity queries and beyond using hub labels, Distance and routing labeling schemes for cube-free median graphs, Sublinear search spaces for shortest path planning in grid and road networks, How to use spanning trees to navigate in graphs, Proof labeling schemes, Additive spanners and distance and routing labeling schemes for hyperbolic graphs, Labeling schemes for weighted dynamic trees, Finding the size and the diameter of a radio network using short labels, Lower and upper bounds for deterministic convergecast with labeling schemes, On the Complexity of Hub Labeling (Extended Abstract), VC-Dimension and Shortest Path Algorithms, How to Use Spanning Trees to Navigate in Graphs, Distance Labeling for Permutation Graphs, A Simple and Optimal Ancestry Labeling Scheme for Trees
