Geodesic
On Compact Encoding of Pagenumber $k$ Graphs
Discrete mathematics & theoretical computer science, Tome 10 (2007-2008) no. 3.

Voir la notice de l'article provenant de la source Episciences

In this paper we show an information-theoretic lower bound of kn - o(kn) 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 + o(kn+m) bits (m the number of edges), that is 4kn + 2n + o(kn) bits in the worst-case. For m-edge graphs of pagenumber k (with multi-edges and loops), we propose a 2mlog2k + O(m) 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 o(m log k) bits, our coding supports (1) the computation of the degree of a node in constant time, (2) adjacency queries with O(logk) queries of type rank, select and match, that is in O(logk *minlogk / loglogm, loglogk) time and (3) the access to δ neighbors in O(δ) runs of select, rank or match;. 
@article{DMTCS_2008_10_3_a9,
     author = {Gavoille, Cyril and Hanusse, Nicolas},
     title = {On {Compact} {Encoding} of {Pagenumber} $k$ {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {10},
     number = {3},
     year = {2007-2008},
     doi = {10.46298/dmtcs.436},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.436/}
}
TY  - JOUR
AU  - Gavoille, Cyril
AU  - Hanusse, Nicolas
TI  - On Compact Encoding of Pagenumber $k$ Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2007-2008
VL  - 10
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.436/
DO  - 10.46298/dmtcs.436
LA  - en
ID  - DMTCS_2008_10_3_a9
ER  - 
%0 Journal Article
%A Gavoille, Cyril
%A Hanusse, Nicolas
%T On Compact Encoding of Pagenumber $k$ Graphs
%J Discrete mathematics & theoretical computer science
%D 2007-2008
%V 10
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.436/
%R 10.46298/dmtcs.436
%G en
%F DMTCS_2008_10_3_a9
Gavoille, Cyril; Hanusse, Nicolas. On Compact Encoding of Pagenumber $k$ Graphs. Discrete mathematics & theoretical computer science, Tome 10 (2007-2008) no. 3. doi : 10.46298/dmtcs.436. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.436/

Cité par Sources :