View in EDS PDF Full Text

On Compact Encoding of Pagenumber k Graphs.

Saved in:
Bibliographic Details
Title: On Compact Encoding of Pagenumber k Graphs.
Authors: Gavoille, Cyril1 gavoille@labri.fr, Hanusse, Nicolas1 hanusse@labri.fr
Source: Discrete Mathematics & Theoretical Computer Science (DMTCS). Dec2008, Vol. 10 Issue 3, p23-34. 12p. 3 Diagrams.
Subjects: Encoding, Paging (Computer science), Graphic methods, Embeddings (Mathematics), Routing (Computer network management)
Abstract: 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 2m log2 k + O(m) bits encoding improving the best previous upper bound of Munro and Raman whenever m ≤ &frac;kn/log2 k. Actually our scheme applies to k-page embedding containing multi-edge and loops. Moreover, with an auxiliary table of o(mlog k) bits, our coding supports (1) the computation of the degree of a node in constant time, (2) adjacency queries with O(log k) queries of type rank; select and match, that is in O(log k ⋅ min {log k= log log m; log log k}) time and (3) the access to δ neighbors in O(δ) runs of select; rank or match. [ABSTRACT FROM AUTHOR]
Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Links:
  – Type: pdflink
Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 41020756
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On Compact Encoding of Pagenumber k Graphs.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Gavoille%2C+Cyril%22">Gavoille, Cyril</searchLink><relatesTo>1</relatesTo><i> gavoille@labri.fr</i><br /><searchLink fieldCode="AR" term="%22Hanusse%2C+Nicolas%22">Hanusse, Nicolas</searchLink><relatesTo>1</relatesTo><i> hanusse@labri.fr</i>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22Discrete+Mathematics+%26+Theoretical+Computer+Science+%28DMTCS%29%22">Discrete Mathematics & Theoretical Computer Science (DMTCS)</searchLink>. Dec2008, Vol. 10 Issue 3, p23-34. 12p. 3 Diagrams.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Encoding%22">Encoding</searchLink><br /><searchLink fieldCode="DE" term="%22Paging+%28Computer+science%29%22">Paging (Computer science)</searchLink><br /><searchLink fieldCode="DE" term="%22Graphic+methods%22">Graphic methods</searchLink><br /><searchLink fieldCode="DE" term="%22Embeddings+%28Mathematics%29%22">Embeddings (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Routing+%28Computer+network+management%29%22">Routing (Computer network management)</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: 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 2m log2 k + O(m) bits encoding improving the best previous upper bound of Munro and Raman whenever m ≤ &frac;kn/log2 k. Actually our scheme applies to k-page embedding containing multi-edge and loops. Moreover, with an auxiliary table of o(mlog k) bits, our coding supports (1) the computation of the degree of a node in constant time, (2) adjacency queries with O(log k) queries of type rank; select and match, that is in O(log k ⋅ min {log k= log log m; log log k}) time and (3) the access to δ neighbors in O(δ) runs of select; rank or match. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of Discrete Mathematics & Theoretical Computer Science (DMTCS) is the property of Discrete Mathematics & Theoretical Computer Science DMTCS and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=41020756
RecordInfo BibRecord:
  BibEntity:
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 12
        StartPage: 23
    Subjects:
      – SubjectFull: Encoding
        Type: general
      – SubjectFull: Paging (Computer science)
        Type: general
      – SubjectFull: Graphic methods
        Type: general
      – SubjectFull: Embeddings (Mathematics)
        Type: general
      – SubjectFull: Routing (Computer network management)
        Type: general
    Titles:
      – TitleFull: On Compact Encoding of Pagenumber k Graphs.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Gavoille, Cyril
      – PersonEntity:
          Name:
            NameFull: Hanusse, Nicolas
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 12
              Text: Dec2008
              Type: published
              Y: 2008
          Identifiers:
            – Type: issn-print
              Value: 13658050
          Numbering:
            – Type: volume
              Value: 10
            – Type: issue
              Value: 3
          Titles:
            – TitleFull: Discrete Mathematics & Theoretical Computer Science (DMTCS)
              Type: main
ResultId 1