On Compact Encoding of Pagenumber $k$ Graphs
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | HANUSSE, Nicolas | |
| dc.date.accessioned | 2024-04-15T09:51:28Z | |
| dc.date.available | 2024-04-15T09:51:28Z | |
| dc.date.created | 2008 | |
| dc.date.issued | 2008-01-01 | |
| dc.identifier.issn | 1462-7264 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198432 | |
| dc.description.abstractEn | 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;. | |
| dc.language.iso | en | |
| dc.publisher | DMTCS | |
| dc.title.en | On Compact Encoding of Pagenumber $k$ Graphs | |
| dc.type | Article de revue | |
| dc.identifier.doi | 10.46298/dmtcs.436 | |
| dc.subject.hal | Informatique [cs]/Mathématique discrète [cs.DM] | |
| bordeaux.journal | Discrete Mathematics and Theoretical Computer Science | |
| bordeaux.page | 23-34 | |
| bordeaux.volume | Vol. 10 no. 3 | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.issue | 3 | |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | hal-00402218 | |
| hal.version | 1 | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//hal-00402218v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Discrete%20Mathematics%20and%20Theoretical%20Computer%20Science&rft.date=2008-01-01&rft.volume=Vol.%2010%20no.%203&rft.issue=3&rft.spage=23-34&rft.epage=23-34&rft.eissn=1462-7264&rft.issn=1462-7264&rft.au=GAVOILLE,%20Cyril&HANUSSE,%20Nicolas&rft.genre=article |
Files in this item
| Files | Size | Format | View |
|---|---|---|---|
|
There are no files associated with this item. |
|||