On Compact Encoding of Pagenumber $k$ GraphsReport as inadecuate

On Compact Encoding of Pagenumber $k$ Graphs - Download this document for free, or read online. Document in PDF available to download.

1 LaBRI - Laboratoire Bordelais de Recherche en Informatique 2 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d-Électronique, Informatique et Radiocommunications de Bordeaux ENSEIRB, CNRS - Centre National de la Recherche Scientifique : UMR5800

Abstract : In this paper we show an information-theoretic lower bound of kn - okn on the minimum number of bits to represent an unlabeled simple connected n-node graph of pagenumber k. This has to be compared with the efficient encoding scheme of Munro and Raman of 2kn + 2m + okn+m bits m the number of edges, that is 4kn + 2n + okn bits in the worst-case. For m-edge graphs of pagenumber k with multi-edges and loops, we propose a 2mlog2k + Om bits encoding improving the best previous upper bound of Munro and Raman whenever m ≤ 1 - 2kn-log2 k. Actually our scheme applies to k-page embedding containing multi-edge and loops. Moreover, with an auxiliary table of om log k bits, our coding supports 1 the computation of the degree of a node in constant time, 2 adjacency queries with Ologk queries of type rank, select and match, that is in Ologk *minlogk - loglogm, loglogk time and 3 the access to δ neighbors in Oδ runs of select, rank or match;.

Author: Cyril Gavoille - Nicolas Hanusse -

Source: https://hal.archives-ouvertes.fr/


Related documents