Implicat Representation of Graphs
- 1 November 1992
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 5 (4) , 596-603
- https://doi.org/10.1137/0405049
Abstract
How to represent a graph in memory is a fundamental data structuring question. Inthe usual representations of an n-vertex graph, the names of the vertices (i.e. integersfrom 1 to n) betray nothing about the graph itself. Indeed, the names (or labels) onthe n vertices are just log n bit place holders to allow data on the edges to encode thestructure of the graph. In our scenario, there is no such waste. By assigning O(log n)bit labels to the vertices, we completely encode the structure ...Keywords
This publication has 11 references indexed in Scilit:
- Universal graphs and induced‐universal graphsJournal of Graph Theory, 1990
- A trade-off between space and efficiency for routing tablesJournal of the ACM, 1989
- Universal Graphs for Bounded-Degree Trees and Planar GraphsSIAM Journal on Discrete Mathematics, 1989
- Intersection graphs of paths in a treeJournal of Combinatorial Theory, Series B, 1986
- Labelling and Implicit Routing in NetworksThe Computer Journal, 1985
- A network flow solution to some nonlinear 0‐1 programming problems, with applications to graph theoryNetworks, 1982
- A recognition algorithm for the intersection graphs of paths in treesDiscrete Mathematics, 1978
- An unexpected result in coding the vertices of a graphJournal of Mathematical Analysis and Applications, 1967
- Coding the vertexes of a graphIEEE Transactions on Information Theory, 1966
- Edge-Disjoint Spanning Trees of Finite GraphsJournal of the London Mathematical Society, 1961