Bijective Linear Time Coding and Decoding for k-Trees View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2010-02

AUTHORS

Saverio Caminiti, Emanuele G. Fusco, Rossella Petreschi

ABSTRACT

The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 Rényi and Rényi generalized the Prüfer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or Rényi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in linear time with respect to the size of the k-tree. More... »

PAGES

284-300

References to SciGraph publications

  • 2004. A Unified Approach to Coding Labeled Trees in LATIN 2004: THEORETICAL INFORMATICS
  • 2007. A Bijective Code for k-Trees with Linear Time Encoding and Decoding in COMBINATORICS, ALGORITHMS, PROBABILISTIC AND EXPERIMENTAL METHODOLOGIES
  • 2005. String Coding of Trees with Locality and Heritability in COMPUTING AND COMBINATORICS
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-008-9131-0

    DOI

    http://dx.doi.org/10.1007/s00224-008-9131-0

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1044638546


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Computer Science Department, University of Rome \u201cLa Sapienza\u201d, via Salaria, 113-00198, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Caminiti", 
            "givenName": "Saverio", 
            "id": "sg:person.010013323122.87", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Computer Science Department, University of Rome \u201cLa Sapienza\u201d, via Salaria, 113-00198, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fusco", 
            "givenName": "Emanuele G.", 
            "id": "sg:person.013526501407.57", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013526501407.57"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Computer Science Department, University of Rome \u201cLa Sapienza\u201d, via Salaria, 113-00198, Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Petreschi", 
            "givenName": "Rossella", 
            "id": "sg:person.011402427702.78", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0012-365x(74)90042-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000114920"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0097-3165(93)90021-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1009445876"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(75)90082-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032770863"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0012-365x(71)90023-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037464722"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.endm.2005.06.024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038284270"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0097-3165(86)90004-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038613771"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74450-4_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039278055", 
              "https://doi.org/10.1007/978-3-540-74450-4_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24698-5_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043716409", 
              "https://doi.org/10.1007/978-3-540-24698-5_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24698-5_38", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043716409", 
              "https://doi.org/10.1007/978-3-540-24698-5_38"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0021-9800(69)80120-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044470945"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0021-9800(69)80119-5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044576158"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11533719_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047625411", 
              "https://doi.org/10.1007/11533719_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11533719_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047625411", 
              "https://doi.org/10.1007/11533719_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0304-3975(97)00228-4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051091799"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1073/pnas.87.24.9635", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052022098"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.tcs.2007.03.009", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053662883"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/s030500410002853x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1054084145"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1112/s002557930000245x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062055384"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/4838", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098912803"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010-02", 
        "datePublishedReg": "2010-02-01", 
        "description": "The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 R\u00e9nyi and R\u00e9nyi generalized the Pr\u00fcfer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or R\u00e9nyi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in linear time with respect to the size of the k-tree.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s00224-008-9131-0", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "46"
          }
        ], 
        "name": "Bijective Linear Time Coding and Decoding for k-Trees", 
        "pagination": "284-300", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "d4a16d84af8e36f1a9caee322d38cba795d6f695115955da22e08d11f8c535c3"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-008-9131-0"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1044638546"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-008-9131-0", 
          "https://app.dimensions.ai/details/publication/pub.1044638546"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-11T14:29", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000373_0000000373/records_13087_00000001.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007/s00224-008-9131-0"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9131-0'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9131-0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9131-0'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9131-0'


     

    This table displays all metadata directly associated to this object as RDF triples.

    129 TRIPLES      21 PREDICATES      44 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-008-9131-0 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N333f51ebf537434ebcd63824818b036b
    4 schema:citation sg:pub.10.1007/11533719_27
    5 sg:pub.10.1007/978-3-540-24698-5_38
    6 sg:pub.10.1007/978-3-540-74450-4_37
    7 https://doi.org/10.1016/0012-365x(71)90023-9
    8 https://doi.org/10.1016/0012-365x(74)90042-9
    9 https://doi.org/10.1016/0012-365x(75)90082-5
    10 https://doi.org/10.1016/0097-3165(86)90004-x
    11 https://doi.org/10.1016/0097-3165(93)90021-y
    12 https://doi.org/10.1016/j.endm.2005.06.024
    13 https://doi.org/10.1016/j.tcs.2007.03.009
    14 https://doi.org/10.1016/s0021-9800(69)80119-5
    15 https://doi.org/10.1016/s0021-9800(69)80120-1
    16 https://doi.org/10.1016/s0304-3975(97)00228-4
    17 https://doi.org/10.1017/s030500410002853x
    18 https://doi.org/10.1073/pnas.87.24.9635
    19 https://doi.org/10.1112/s002557930000245x
    20 https://doi.org/10.1142/4838
    21 schema:datePublished 2010-02
    22 schema:datePublishedReg 2010-02-01
    23 schema:description The problem of coding labeled trees has been widely studied in the literature and several bijective codes that realize associations between labeled trees and sequences of labels have been presented. k-trees are one of the most natural and interesting generalizations of trees and there is considerable interest in developing efficient tools to manipulate this class of graphs, since many NP-Complete problems have been shown to be polynomially solvable on k-trees and partial k-trees. In 1970 Rényi and Rényi generalized the Prüfer code, the first bijective code for trees, to a subset of labeled k-trees. Subsequently, non redundant codes that realize bijection between k-trees (or Rényi k-trees) and a well defined set of strings were produced. In this paper we introduce a new bijective code for labeled k-trees which, to the best of our knowledge, produces the first coding and decoding algorithms running in linear time with respect to the size of the k-tree.
    24 schema:genre research_article
    25 schema:inLanguage en
    26 schema:isAccessibleForFree true
    27 schema:isPartOf N158c4cb240604b4c956d3483f68c3f71
    28 N23972244039644c0adf4f9ae2494d35d
    29 sg:journal.1052098
    30 schema:name Bijective Linear Time Coding and Decoding for k-Trees
    31 schema:pagination 284-300
    32 schema:productId N17081629767448a68405bda4c7e80a60
    33 N5215a296c8d14b229dac528ced7da059
    34 Nf6647c345bca472faa0bcbcf12a1d6a4
    35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044638546
    36 https://doi.org/10.1007/s00224-008-9131-0
    37 schema:sdDatePublished 2019-04-11T14:29
    38 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    39 schema:sdPublisher Na6c2e721e88647c984cbf7c15e58f2e6
    40 schema:url http://link.springer.com/10.1007/s00224-008-9131-0
    41 sgo:license sg:explorer/license/
    42 sgo:sdDataset articles
    43 rdf:type schema:ScholarlyArticle
    44 N158c4cb240604b4c956d3483f68c3f71 schema:issueNumber 2
    45 rdf:type schema:PublicationIssue
    46 N17081629767448a68405bda4c7e80a60 schema:name readcube_id
    47 schema:value d4a16d84af8e36f1a9caee322d38cba795d6f695115955da22e08d11f8c535c3
    48 rdf:type schema:PropertyValue
    49 N23972244039644c0adf4f9ae2494d35d schema:volumeNumber 46
    50 rdf:type schema:PublicationVolume
    51 N333f51ebf537434ebcd63824818b036b rdf:first sg:person.010013323122.87
    52 rdf:rest Neeec89899b294edfb4d833542b1b30e3
    53 N5215a296c8d14b229dac528ced7da059 schema:name doi
    54 schema:value 10.1007/s00224-008-9131-0
    55 rdf:type schema:PropertyValue
    56 Na4faf0b66b6c452ca7d9684d3e1479f2 rdf:first sg:person.011402427702.78
    57 rdf:rest rdf:nil
    58 Na6c2e721e88647c984cbf7c15e58f2e6 schema:name Springer Nature - SN SciGraph project
    59 rdf:type schema:Organization
    60 Neeec89899b294edfb4d833542b1b30e3 rdf:first sg:person.013526501407.57
    61 rdf:rest Na4faf0b66b6c452ca7d9684d3e1479f2
    62 Nf6647c345bca472faa0bcbcf12a1d6a4 schema:name dimensions_id
    63 schema:value pub.1044638546
    64 rdf:type schema:PropertyValue
    65 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    66 schema:name Information and Computing Sciences
    67 rdf:type schema:DefinedTerm
    68 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    69 schema:name Data Format
    70 rdf:type schema:DefinedTerm
    71 sg:journal.1052098 schema:issn 1432-4350
    72 1433-0490
    73 schema:name Theory of Computing Systems
    74 rdf:type schema:Periodical
    75 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    76 schema:familyName Caminiti
    77 schema:givenName Saverio
    78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
    79 rdf:type schema:Person
    80 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    81 schema:familyName Petreschi
    82 schema:givenName Rossella
    83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    84 rdf:type schema:Person
    85 sg:person.013526501407.57 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    86 schema:familyName Fusco
    87 schema:givenName Emanuele G.
    88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013526501407.57
    89 rdf:type schema:Person
    90 sg:pub.10.1007/11533719_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047625411
    91 https://doi.org/10.1007/11533719_27
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/978-3-540-24698-5_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043716409
    94 https://doi.org/10.1007/978-3-540-24698-5_38
    95 rdf:type schema:CreativeWork
    96 sg:pub.10.1007/978-3-540-74450-4_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039278055
    97 https://doi.org/10.1007/978-3-540-74450-4_37
    98 rdf:type schema:CreativeWork
    99 https://doi.org/10.1016/0012-365x(71)90023-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037464722
    100 rdf:type schema:CreativeWork
    101 https://doi.org/10.1016/0012-365x(74)90042-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000114920
    102 rdf:type schema:CreativeWork
    103 https://doi.org/10.1016/0012-365x(75)90082-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032770863
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0097-3165(86)90004-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1038613771
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1016/0097-3165(93)90021-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1009445876
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1016/j.endm.2005.06.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038284270
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.1016/j.tcs.2007.03.009 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053662883
    112 rdf:type schema:CreativeWork
    113 https://doi.org/10.1016/s0021-9800(69)80119-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044576158
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1016/s0021-9800(69)80120-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044470945
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1016/s0304-3975(97)00228-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051091799
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1017/s030500410002853x schema:sameAs https://app.dimensions.ai/details/publication/pub.1054084145
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1073/pnas.87.24.9635 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052022098
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1112/s002557930000245x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062055384
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1142/4838 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098912803
    126 rdf:type schema:CreativeWork
    127 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    128 schema:name Computer Science Department, University of Rome “La Sapienza”, via Salaria, 113-00198, Rome, Italy
    129 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...