Proximity-preserving labeling schemes

DOI<167::AID-JGT7>3.0.CO;2-5 10.1002/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5zbMath0945.05052OpenAlexW4232548171MaRDI QIDQ4948512

David Peleg

Publication date: 8 October 2000

Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(200003)33:3<167::aid-jgt7>3.0.co;2-5

zbMATH Keywords

distancegraph representationproximity preserving labeling scheme

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

Tree-decompositions with bags of small diameter ⋮ Small Stretch Pairwise Spanners and Approximate $D$-Preservers ⋮ How to use spanning trees to navigate in graphs ⋮ The space complexity of sum labelling ⋮ Proof labeling schemes ⋮ Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas ⋮ Additive Spanners for Circle Graphs and Polygonal Graphs ⋮ How to Use Spanning Trees to Navigate in Graphs ⋮ Adjacency Labeling Schemes and Induced-Universal Graphs ⋮ On the Complexity of Hub Labeling (Extended Abstract) ⋮ New pairwise spanners ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ A note on exact distance labeling ⋮ Collective additive tree spanners for circle graphs and polygonal graphs ⋮ Distance labeling scheme and split decomposition ⋮ Distance and routing labeling schemes for cube-free median graphs ⋮ On efficient distributed construction of near optimal routing schemes ⋮ Space-efficient path-reporting approximate distance oracles ⋮ Shortest-path queries in static networks ⋮ Interval routing in reliability networks ⋮ The space complexity of sum labelling ⋮ Unnamed Item ⋮ The Greedy Spanner Is Existentially Optimal ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Localized and compact data-structure for comparability graphs ⋮ A note on labeling schemes for graph connectivity ⋮ Unnamed Item ⋮ Decomposing a graph into shortest paths with bounded eccentricity ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Distance Labeling for Permutation Graphs

Cites Work

• On Lipschitz embedding of finite metric spaces in Hilbert space
• The geometry of graphs and some of its algorithmic applications
• An unexpected result in coding the vertices of a graph
• Space-Efficient Message Routing inc-Decomposable Networks
• Coding the vertexes of a graph
• Unnamed Item
• Unnamed Item
• Unnamed Item