Optimal Distance Labeling for Interval Graphs and Related Graph Families

DOI10.1137/050635006zbMath1197.05097MaRDI QIDQ3395001

Cyril Gavoille, Christophe Paul

Publication date: 20 August 2009

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/050635006

zbMATH Keywords

distance in graphs; graph representation; distance labeling scheme; distributed data-structure

Mathematics Subject Classification ID

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

05C12: Distance in graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

05C62: Graph representations (geometric and intersection representations, etc.)

Related Items

On the OBDD representation of some graph classes, Additive spanners and distance and routing labeling schemes for hyperbolic graphs, Interval Routing Schemes for Circular-Arc Graphs