Near-optimal induced universal graphs for cycles and paths

DOI10.1016/j.dam.2019.10.030zbMath1444.05119OpenAlexW2985914372WikidataQ126836412 ScholiaQ126836412MaRDI QIDQ2185721

Stephen Alstrup, Morten Stöckel, Mikkel Abrahamsen, Mathias Bæk Tejs Knudsen, Jacob Holm

Publication date: 5 June 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.10.030

zbMATH Keywords

bounded degree graphsdistributed computinginduced universal graphsadjacency labeling schemes

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Related Items

Shorter Labeling Schemes for Planar Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asymptotically optimal induced universal graphs
• Induced-universal graphs for graphs with bounded maximum degree
• On induced-universal graphs for the class of bounded-degree graphs
• Asymptotic enumeration by degree sequence of graphs with degrees \(o(n^{1/2})\)
• Asymptotic enumeration by degree sequence of graphs of high degree
• Labeling schemes for weighted dynamic trees
• Compact Routing with Minimum Stretch
• Adjacency Labeling Schemes and Induced-Universal Graphs
• Labeling Dynamic XML Trees
• Labelling and Implicit Routing in Networks
• Universal graphs and induced-universal graphs
• Shorter Implicit Representation for Planar Graphs and Bounded Treewidth Graphs
• Approximate distance oracles
• Implicat Representation of Graphs
• Optimal induced universal graphs for bounded-degree graphs
• Optimal Induced Universal Graphs and Adjacency Labeling for Trees
• Compact routing schemes with low stretch factor
• Near-Optimal Induced Universal Graphs for Bounded Degree Graphs
• Compact and localized distributed data structures
• On minimal n-universal graphs

This page was built for publication: Near-optimal induced universal graphs for cycles and paths