Logical labeling schemes

DOI10.1016/J.DISC.2023.113565MaRDI QIDQ6172301zbMATH OpenOpenAlexFDO

Authors Maurice Chandoo

Publication date 19 July 2023

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://www.repo.uni-hannover.de/handle/123456789/12057

zbMATH Keywords

graph class reductionimplicit representationsstructural graph theory

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Data structures (68P05) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Distance labeling schemes for well-separated graph classes
• scientific article; zbMATH DE number 1500540
• Labeling schemes for bounded degree graphs
• Adjacency Labelling for Planar Graphs (and Beyond)
• Brief announcement: Labeling schemes for power-law graphs

Cites work

• A counter-example to the probabilistic universal graph conjecture via randomized communication complexity
• A semi-algebraic version of Zarankiewicz's problem
• Adjacency Labelling for Planar Graphs (and Beyond)
• Boundary properties of factorial classes of graphs
• Dot product representations of graphs
• Efficient graph representations
• Graph functionality
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 6851856 (Why is no real title available?)
• scientific article; zbMATH DE number 7650381 (Why is no real title available?)
• Implicat Representation of Graphs
• Integer realizations of disk and segment graphs
• Logical number theory I. An introduction
• Optimal induced universal graphs and adjacency labeling for trees
• Optimal labelling schemes for adjacency, comparability, and reachability
• Sphere and dot product representations of graphs
• The speed of hereditary properties of graphs
• The structure and the number of \(P_7\)-free bipartite graphs

Cited in

(10)

• Efficient First-Order Model-Checking Using Short Labels
• Brief announcement: Labeling schemes for power-law graphs
• Labeling Schemes with Queries
• Constructing Labeling Schemes Through Universal Matrices
• Logical Mappings
• Compact labelings for efficient first-order model-checking
• Small but unwieldy: a lower bound on adjacency labels for small classes
• Tight bounds on adjacency labels for monotone graph classes
• Randomized communication and implicit graph representations
• Constructing labeling schemes through universal matrices

This page was built for publication: Logical labeling schemes

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