Optimal Distance Labeling for Interval Graphs and Related Graph Families

DOI10.1137/050635006MaRDI QIDQ3395001zbMATH OpenOpenAlexFDO

Authors 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 graphsdistance labeling schemedistributed data-structuregraph representation

Mathematics Subject Classification ID

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

Recommendations

• Optimal distance labeling for interval and circular-arc graphs
• Distance labeling schemes for well-separated graph classes
• Approximate distance labeling schemes
• scientific article; zbMATH DE number 1500540
• Simpler, faster and shorter labels for distances in graphs

Cited in

(25)

• Distance labeling scheme and split decomposition
• Distance labeling schemes for well-separated graph classes
• Succinct navigational oracles for families of intersection graphs on a circle
• Distance labeling schemes for \(K_4\)-free bridged graphs
• Distance and routing labeling schemes for cube-free median graphs
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Compact representation of interval graphs and circular-arc graphs of bounded degree and chromatic number
• Succinct permutation graphs
• Approximate distance labeling schemes
• Interval routing schemes for circular-arc graphs
• On the OBDD representation of some graph classes
• Realizing Interval Graphs with Size and Distance Constraints
• scientific article; zbMATH DE number 1500540 (Why is no real title available?)
• Distance labeling schemes for cube-free median graphs
• Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs
• Shorter Labeling Schemes for Planar Graphs
• Optimal distance labeling for interval and circular-arc graphs
• scientific article; zbMATH DE number 7765383 (Why is no real title available?)
• Balancing graph Voronoi diagrams with one more vertex
• Distance queries over dynamic interval graphs
• Distance labeling for families of cycles
• Closing the gap: minimum space optimal time distance labeling scheme for interval graphs
• Distance queries over dynamic interval graphs
• Enumeration of interval graphs and d-representable complexes
• Optimal distance labeling for permutation graphs

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

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