Proximity-preserving labeling schemes

DOI10.1002/(SICI)1097-0118(200003)33:3%3C167::AID-JGT7%3E3.0.CO;2-5MaRDI QIDQ4948512zbMATH OpenOpenAlexFDO

Authors David Peleg

Publication date 8 October 2000

Full work available at URL https://doi.org/10.1002/(sici)1097-0118(200003)33:3%3C167::aid-jgt7%3E3.0.co;2-5

zbMATH Keywords

distancegraph representationproximity preserving labeling scheme

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1420896
• Distance labeling in graphs (extended abstract)
• Distance labeling in graphs
• Simpler, faster and shorter labels for distances in graphs
• A note on exact distance labeling
• Labeling Schemes for Small Distances in Trees
• scientific article; zbMATH DE number 2079400
• Sublinear Distance Labeling
• scientific article; zbMATH DE number 1875437
• Algorithms and Computation

Cites work

• An unexpected result in coding the vertices of a graph
• Coding the vertexes of a graph
• scientific article; zbMATH DE number 1500540 (Why is no real title available?)
• scientific article; zbMATH DE number 1775450 (Why is no real title available?)
• scientific article; zbMATH DE number 1420896 (Why is no real title available?)
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Space-Efficient Message Routing inc-Decomposable Networks
• The geometry of graphs and some of its algorithmic applications

Cited in

(46)

• A note on models for graph representations
• Localized and compact data-structure for comparability graphs
• Distance labeling scheme and split decomposition
• New pairwise spanners
• On efficient distributed construction of near optimal routing schemes
• Interval routing in reliability networks
• A note on exact distance labeling
• The space complexity of sum labelling
• Distance and routing labeling schemes for cube-free median graphs
• Tree-decompositions with bags of small diameter
• How to use spanning trees to navigate in graphs
• Proof labeling schemes
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Informative labeling schemes for graphs
• On the complexity of hub labeling (extended abstract)
• How to Use Spanning Trees to Navigate in Graphs
• Distance Labeling for Permutation Graphs
• Small stretch pairwise spanners and approximate D-preservers
• Collective additive tree spanners for circle graphs and polygonal graphs
• scientific article; zbMATH DE number 2079400 (Why is no real title available?)
• scientific article; zbMATH DE number 1759444 (Why is no real title available?)
• Adjacency labeling schemes and induced-universal graphs
• scientific article; zbMATH DE number 1875437 (Why is no real title available?)
• scientific article; zbMATH DE number 1420896 (Why is no real title available?)
• The greedy spanner is existentially optimal
• Distance labeling schemes for cube-free median graphs
• Decomposing a graph into shortest paths with bounded eccentricity
• Distance Labels with Optimal Local Stretch
• Space-efficient path-reporting approximate distance oracles
• Shortest-path queries in static networks
• Additive Spanners for Circle Graphs and Polygonal Graphs
• Shortest reconfiguration paths in the solution space of Boolean formulas
• Brief announcement: Labeling schemes for power-law graphs
• Labeling Schemes with Queries
• Labeling Schemes for Small Distances in Trees
• Fault-tolerant distance labeling for planar graphs
• Fault-tolerant distance labeling for planar graphs
• The space complexity of sum labelling
• Exact and approximate hierarchical hub labeling
• A unified framework of light spanners. I: Fast (yet optimal) constructions
• Optimal Euclidean tree covers
• Lipschitz decompositions of finite _p metrics
• Exact and approximate hierarchical hub labeling
• Optimal distance labeling for permutation graphs
• A note on labeling schemes for graph connectivity
• Decomposing a graph into shortest paths with bounded eccentricity

This page was built for publication: Proximity-preserving labeling schemes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4948512)