Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs

DOI10.1016/S1571-0653(04)00374-9MaRDI QIDQ3438963zbMATH OpenOpenAlexFDO

Authors Cyril Gavoille, Christophe Paul

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s1571-0653(04)00374-9

zbMATH Keywords

distance hereditary graphsdistance labelling schemesplit decomposition

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Distance labeling scheme and split decomposition
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• A linear-time algorithm for connectedr-domination and Steiner tree on distance-hereditary graphs
• Distance-hereditary comparability graphs

Cited in

(13)

• Distance labeling scheme and split decomposition
• Distance-hereditary comparability graphs
• General compact labeling schemes for dynamic trees
• Randomized proof-labeling schemes
• Labeling schemes for weighted dynamic trees
• Distance-hereditary comparability graphs
• Using split composition to extend distance-hereditary graphs in a generative way (extended abstract)
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Compact and localized distributed data structures
• An exact enumeration of distance-hereditary graphs
• Dynamic Distance Hereditary Graphs Using Split Decomposition
• A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
• Constructing labeling schemes through universal matrices

This page was built for publication: Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs

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