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

split decompositiondistance hereditary graphsdistance labelling scheme

Mathematics Subject Classification ID

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

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

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)