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