Distance and routing labeling schemes for non-positively curved plane graphs

DOI10.1016/J.JALGOR.2004.07.011zbMATH Open1134.05331OpenAlexW2153353483MaRDI QIDQ3414546FDOQ3414546

Authors: Victor Chepoi, Feodor F. Dragan, Yann Vaxès 

Publication date: 9 January 2007

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jalgor.2004.07.011

Recommendations

• Distance labeling in graphs (extended abstract)
• Better distance labeling for unweighted planar graphs
• Better distance labeling for unweighted planar graphs
• Distance labellings of graphs
• Algorithms and Computation
• Distance constrained labelings of planar graphs with no short cycles
• On distance irregular labelling of graphs
• Labeling of planar graphs with a condition on distance two
• Fault-tolerant distance labeling for planar graphs
• Fault-tolerant distance labeling for planar graphs

zbMATH Keywords

planar graphsefficient algorithmsdistance labeling schemerouting labeling scheme

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cited In (17)

• Localized and compact data-structure for comparability graphs
• ALGORITHMS FOR DISTANCE PROBLEMS IN PLANAR COMPLEXES OF GLOBAL NONPOSITIVE CURVATURE
• Polyhexes that are \(\ell _1\) graphs
• Title not available (Why is that?)
• Isometric embedding of Busemann surfaces into \(L_1\)
• Implicit representation of relations
• Exact Distance Labelings Yield Additive-Stretch Compact Routing Schemes
• Algorithms and Computation
• Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Distance and routing labeling schemes for cube-free median graphs
• \(l_1\)-embeddability of generic quadrilateral Möbius maps
• Convex excess in partial cubes
• On finding convex cuts in general, bipartite and plane graphs
• Distributed Relationship Schemes for Trees
• Distance labeling schemes for \(K_4\)-free bridged graphs
• Shortest paths and convex hulls in 2D complexes with non-positive curvature

This page was built for publication: Distance and routing labeling schemes for non-positively curved plane graphs

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