Adjacency Labeling Schemes and Induced-Universal Graphs
From MaRDI portal
Publication:2941558
DOI10.1145/2746539.2746545zbMath1321.05226arXiv1404.3391OpenAlexW2115083710MaRDI QIDQ2941558
Haim Kaplan, Mikkel Thorup, Uri Zwick, Stephen Alstrup
Publication date: 21 August 2015
Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.3391
Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Directed graphs (digraphs), tournaments (05C20)
Related Items (12)
Better distance labeling for unweighted planar graphs ⋮ A Simple and Optimal Ancestry Labeling Scheme for Trees ⋮ An adjacency labeling scheme based on a decomposition of trees into caterpillars ⋮ Supertrees ⋮ Near-optimal induced universal graphs for cycles and paths ⋮ Optimal induced universal graphs for bounded-degree graphs ⋮ Unnamed Item ⋮ Induced Universal Hypergraphs ⋮ Universality of random permutations ⋮ Better distance labeling for unweighted planar graphs ⋮ Asymptotically optimal induced universal graphs ⋮ Lower bounds for superpatterns and universal sequences
Uses Software
Cites Work
- Ramsey partitions and proximity data structures
- On sparse spanners of weighted graphs
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Approximate distance oracles
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Near-Linear Time Construction of Sparse Neighborhood Covers
- Shortest-path queries in static networks
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Unnamed Item
This page was built for publication: Adjacency Labeling Schemes and Induced-Universal Graphs
