Representing graphs implicitly using almost optimal space

DOI10.1016/S0166-218X(00)00225-0MaRDI QIDQ5928875zbMATH OpenWikidataFDO

Authors Maurizio Talamo, Paola Vocca

Publication date 24 August 2002

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

Full work available at URL https://doi.org/10.1016/S0166-218X(00)00225-0

zbMATH Keywords

adjacency testlabelling

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Theory of data (68P99)

Review text

The authors present a new graph labelling scheme that assigns to each vertex \(v\) of degree \(\delta(v)\) of a graph of order \(n\) a \(O(\delta(v)\log^2n)\) bit label. The adjacency test can be performed in seven steps and the entire scheme can be computed in polynomial time. In addition, the scheme is implicit (without pointers).

Recommendations

• scientific article; zbMATH DE number 1262796
• Implicat Representation of Graphs
• Labeling schemes for bounded degree graphs
• Adjacency Labelling for Planar Graphs (and Beyond)
• Adjacency labeling schemes and induced-universal graphs

Cites work

• A data structure for lattice representation
• A note on succinct representations of graphs
• A trade-off between space and efficiency for routing tables
• Algorithms for parallel memory, I: Two-level memories
• An Efficient Data Structure for Lattice Operations
• An implicit data structure supporting insertion, deletion, and search in O( ^ 2\,n) time
• An unexpected result in coding the vertices of a graph
• Coding the vertexes of a graph
• Designing networks with compact routing tables
• Distributed algorithms. 10th international workshop, WDAG '96, Bologna, Italy, October 9--11, 1996. Proceedings
• Efficient Message Routing in Planar Networks
• scientific article; zbMATH DE number 3940741 (Why is no real title available?)
• scientific article; zbMATH DE number 3481857 (Why is no real title available?)
• scientific article; zbMATH DE number 1262796 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• scientific article; zbMATH DE number 219271 (Why is no real title available?)
• Implicat Representation of Graphs
• Implicit O(1) Probe Search
• Implicit data structures for fast search and update
• Implicit data structures for linear hashing schemes
• Implicit Data Structures for the Dictionary Problem
• Interval Routing
• Labelling and Implicit Routing in Networks
• Memory requirement for routing in distributed networks
• On the succinct representation of graphs
• Optimal routing tables
• Parallel concepts in graph theory
• Representation of graphs
• Space-Efficient Message Routing inc-Decomposable Networks
• Storing a Sparse Table with 0 (1) Worst Case Access Time
• Succinct representations of graphs
• The complexity of searching implicit graphs
• What Can be Computed Locally?

Cited in

(13)

• On the OBDD size for graphs of bounded tree- and clique-width
• Efficient computation of implicit representations of sparse graphs
• Adjacency labeling schemes and induced-universal graphs
• On the OBDD representation of some graph classes
• Succinct posets
• Implicat Representation of Graphs
• scientific article; zbMATH DE number 1262796 (Why is no real title available?)
• On symbolic OBDD-based algorithms for the minimum spanning tree problem
• Adjacency labeling schemes and induced-universal graphs
• Algorithms and Data Structures
• OPTIMAL FOLDING OF DATA FLOW GRAPHS BASED ON FINITE PROJECTIVE GEOMETRY USING VECTOR SPACE PARTITIONING
• Short Labels by Traversal and Jumping
• Trading uninitialized space for time

This page was built for publication: Representing graphs implicitly using almost optimal space

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