Distance and routing labeling schemes for cube-free median graphs

DOI10.1007/S00453-020-00756-WOpenAlexW3041586642MaRDI QIDQ2223698FDOQ2223698

Authors: Victor Chepoi, Arnaud Labourel, Sébastien Ratel 

Publication date: 1 February 2021

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1809.10508

Recommendations

• Distance and routing labeling schemes for non-positively curved plane graphs
• Distance labeling schemes for well-separated graph classes
• scientific article; zbMATH DE number 1500540
• scientific article; zbMATH DE number 1875437
• Proximity-preserving labeling schemes

zbMATH Keywords

labeling schemesmedian graphsdistributed distance computation

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Cites Work

• Geometry of the space of phylogenetic trees
• Introduction to algorithms.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distance labeling in graphs
• Median algebras
• Graphs of some CAT(0) complexes
• Distributed Computing: A Locality-Sensitive Approach
• Title not available (Why is that?)
• The complexity of satisfiability problems
• Retracts of hypercubes
• Title not available (Why is that?)
• The virtual Haken conjecture (with an appendix by Ian Agol, Daniel Groves and Jason Manning).
• Title not available (Why is that?)
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• Implicat Representation of Graphs
• An unexpected result in coding the vertices of a graph
• Informative labeling schemes for graphs
• Title not available (Why is that?)
• Localized and compact data-structure for comparability graphs
• Algorithms and Computation
• Fiber-complemented graphs. I: Structure and invariant subgraphs
• Metric graph theory and geometry: a survey
• Title not available (Why is that?)
• Distance labeling scheme and split decomposition
• Memory requirement for routing in distributed networks
• Proximity-preserving labeling schemes
• Bypassing the embedding
• Median graphs and Helly hypergraphs
• The geometry and topology of reconfiguration
• Nice labeling problem for event structures: a counterexample
• On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes
• Embedding Topological Median Algebras in Products of Dendrons
• Ramified rectilinear polygons: coordinatization by dendrons
• Query efficient implementation of graphs of bounded clique-width
• Optimal scale-free compact routing schemes in networks of low doubling dimension
• Shortest path problem in rectangular complexes of global nonpositive curvature
• On cube-free median graphs
• Proof of the squashed cube conjecture
• Sublinear-space distance labeling using hubs
• Simpler, faster and shorter labels for distances in graphs
• Distance labeling schemes for trees
• Optimal distance labeling schemes for trees
• Collective tree spanners in graphs with bounded parameters
• Distance and routing labeling schemes for non-positively curved plane graphs
• On density of subgraphs of Cartesian products
• A counterexample to Thiagarajan's conjecture on regular event structures
• A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
• Forbidden-set distance labels for graphs of bounded doubling dimension

Cited In (6)

• Sample Compression Schemes for Balls in Graphs
• Title not available (Why is that?)
• Brief announcement: Labeling schemes for power-law graphs
• Planar median graphs and cubesquare-graphs
• On cube-free median graphs
• Distance labeling schemes for \(K_4\)-free bridged graphs

This page was built for publication: Distance and routing labeling schemes for cube-free median graphs

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