An adjacency labeling scheme based on a decomposition of trees into caterpillars

DOI10.1007/978-3-031-06678-8_9MaRDI QIDQ2169946zbMATH OpenOpenAlexFDO

Authors Avah Banerjee

Publication date 30 August 2022

Full work available at URL https://arxiv.org/abs/2201.04749

zbMATH Keywords

clique-widthshereditary classesimplicit representation

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cites work

• A data structure for dynamic trees
• Adjacency labeling schemes and induced-universal graphs
• An unexpected result in coding the vertices of a graph
• Asymptotically optimal induced universal graphs
• Block-graph width
• Coding the vertexes of a graph
• Compact representation of graphs of small clique-width
• Efficient graph representations
• Efficient local representations of graphs
• Graph Classes: A Survey
• Graph structure and monadic second-order logic. A language-theoretic approach
• Handle-rewriting hypergraph grammars
• Implicat Representation of Graphs
• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
• On probe permutation graphs
• On some simple widths
• On the OBDD size for graphs of bounded tree- and clique-width
• Optimal induced universal graphs and adjacency labeling for trees
• Partitioned probe comparability graphs
• Query efficient implementation of graphs of bounded clique-width
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• Sublinear Distance Labeling

Cited in

(2)

• Small but unwieldy: a lower bound on adjacency labels for small classes
• Tight bounds on adjacency labels for monotone graph classes

This page was built for publication: An adjacency labeling scheme based on a decomposition of trees into caterpillars

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