Distance labeling scheme and split decomposition

DOI10.1016/S0012-365X(03)00232-2MaRDI QIDQ1417571zbMATH OpenFDO

Authors Christophe Paul, Cyril Gavoille

Publication date 5 January 2004

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Distance labeling schemeDistance-hereditary graphsSplit decomposition

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Distance labeling schemes for well-separated graph classes
• scientific article; zbMATH DE number 1500540
• Optimal Distance Labeling for Interval Graphs and Related Graph Families
• scientific article; zbMATH DE number 1875437

Cites work

• scientific article; zbMATH DE number 1696525 (Why is no real title available?)
• scientific article; zbMATH DE number 2044923 (Why is no real title available?)
• scientific article; zbMATH DE number 2077119 (Why is no real title available?)
• scientific article; zbMATH DE number 2079400 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 1759444 (Why is no real title available?)
• scientific article; zbMATH DE number 1875437 (Why is no real title available?)
• scientific article; zbMATH DE number 2119757 (Why is no real title available?)
• scientific article; zbMATH DE number 2119759 (Why is no real title available?)
• scientific article; zbMATH DE number 3395950 (Why is no real title available?)
• A Characterization of Certain Ptolemaic Graphs
• Almost distance-hereditary graphs
• An unexpected result in coding the vertices of a graph
• Block-cutvertex trees and block-cutvertex partitions
• Completely separable graphs
• Decomposition of Directed Graphs
• Distance labeling in graphs (extended abstract)
• Graph Classes: A Survey
• Graph minors. III. Planar tree-width
• Graphs with bounded induced distance
• Handle-rewriting hypergraph grammars
• Implicat Representation of Graphs
• Nearest common ancestors: a survey and a new algorithm for a distributed environment
• On Minimal Blocks
• On metric properties of certain clique graphs
• Proximity-preserving labeling schemes
• Query efficient implementation of graphs of bounded clique-width
• Weak bipolarizable graphs

Cited in

(20)

• Optimal centrality computations within bounded clique-width graphs
• Split Decomposition and Distance Labelling: An Optimal Scheme For Distance Hereditary Graphs
• Practical and efficient split decomposition via graph-labelled trees
• Inductive computations on graphs defined by clique-width expressions
• Word-representability of graphs with respect to split recomposition
• scientific article; zbMATH DE number 1420896 (Why is no real title available?)
• Distance Labels with Optimal Local Stretch
• A Labelled System for IPL with Variable Splitting
• Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs
• Distance labeling schemes for \(K_4\)-free bridged graphs
• Distance Labeling for Permutation Graphs
• Sublinear Distance Labeling
• Solving problems on graphs of high rank-width
• Additive spanners and distance and routing labeling schemes for hyperbolic graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Linear rank-width of distance-hereditary graphs. I. A polynomial-time algorithm
• scientific article; zbMATH DE number 7561659 (Why is no real title available?)
• Localized and compact data-structure for comparability graphs
• Distance Labeling Schemes for $$K_4$$-Free Bridged Graphs
• Distance and routing labeling schemes for cube-free median graphs

This page was built for publication: Distance labeling scheme and split decomposition

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