Optimal Distance Labeling for Interval Graphs and Related Graph Families

DOI10.1137/050635006zbMath1197.05097OpenAlexW2023365186MaRDI 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 graphsgraph representationdistance labeling schemedistributed data-structure

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (13)

On the OBDD representation of some graph classes ⋮ Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs ⋮ Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number ⋮ Succinct permutation graphs ⋮ Additive spanners and distance and routing labeling schemes for hyperbolic graphs ⋮ Balancing graph Voronoi diagrams with one more vertex ⋮ Unnamed Item ⋮ Interval Routing Schemes for Circular-Arc Graphs ⋮ Distance and routing labeling schemes for cube-free median graphs ⋮ Unnamed Item ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Distance labeling schemes for \(K_4\)-free bridged graphs

This page was built for publication: Optimal Distance Labeling for Interval Graphs and Related Graph Families