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
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
- 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
- Labeling schemes for vertex connectivity
- 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
