Adjacency Labeling Schemes and Induced-Universal Graphs
From MaRDI portal
Publication:4610450
DOI10.1137/16M1105967zbMath1403.05123OpenAlexW2908688288MaRDI QIDQ4610450
Uri Zwick, Stephen Alstrup, Mikkel Thorup, Haim Kaplan
Publication date: 16 January 2019
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1105967
Analysis of algorithms and problem complexity (68Q25) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)
Related Items (7)
Deterministic size discovery and topology recognition in radio networks with short labels ⋮ Quasipolynomiality of the Smallest Missing Induced Subgraph ⋮ Implicit representation of relations ⋮ Fault-tolerant distance labeling for planar graphs ⋮ Isometric Universal Graphs ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Fault-tolerant distance labeling for planar graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Succinct encoding of arbitrary graphs
- Succinct representations of permutations and functions
- Asymptotically optimal induced universal graphs
- Nearest common ancestors: a survey and a new algorithm for a distributed environment
- Induced-universal graphs for graphs with bounded maximum degree
- On induced-universal graphs for the class of bounded-degree graphs
- Graphs which contain all small graphs
- On graphs which contain all small trees
- A uniform paradigm to succinctly encode various families of trees
- An unexpected result in coding the vertices of a graph
- Changing base without losing space
- An optimal ancestry scheme and small universal posets
- Universal graphs and induced-universal graphs
- Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
- Approximate distance oracles
- Universal Graphs for Bounded-Degree Trees and Planar Graphs
- On Graphs Which Contain All Sparse Graphs
- Implicat Representation of Graphs
- Universal codeword sets and representations of the integers
- On minimal universal graphs for hereditary classes
- Simpler, faster and shorter labels for distances in graphs
- Optimal induced universal graphs for bounded-degree graphs
- Optimal Induced Universal Graphs and Adjacency Labeling for Trees
- Labeling Schemes for Flow and Connectivity
- On Universal Graphs for Spanning Trees
- Compact routing schemes with low stretch factor
- Distance labeling in graphs
- Proximity-preserving labeling schemes
- Compact and localized distributed data structures
- On minimal n-universal graphs
- Near-optimal labeling schemes for nearest common ancestors
- Sparse universal graphs for bounded‐degree graphs
- Compact Labeling Scheme for Ancestor Queries
- Universal graphs and universal functions
- Coding the vertexes of a graph
- SOME UNSOLVED PROBLEMS IN GRAPH THEORY
This page was built for publication: Adjacency Labeling Schemes and Induced-Universal Graphs
