A Bijective Code for k-Trees with Linear Time Encoding and Decoding View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2007

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, 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 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 encoding and decoding algorithms running in linear time with respect to the size of the k-tree. More... »

PAGES

408-420

Book

TITLE

Combinatorics, Algorithms, Probabilistic and Experimental Methodologies

ISBN

978-3-540-74449-8
978-3-540-74450-4

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-74450-4_37

DOI

http://dx.doi.org/10.1007/978-3-540-74450-4_37

DIMENSIONS

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


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(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/0097-3165(86)90004-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1038613771"
        ], 
        "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.1112/s002557930000245x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062055384"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2007", 
    "datePublishedReg": "2007-01-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, 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 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 encoding and decoding algorithms running in linear time with respect to the size of the k-tree.", 
    "editor": [
      {
        "familyName": "Chen", 
        "givenName": "Bo", 
        "type": "Person"
      }, 
      {
        "familyName": "Paterson", 
        "givenName": "Mike", 
        "type": "Person"
      }, 
      {
        "familyName": "Zhang", 
        "givenName": "Guochuan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-74450-4_37", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-74449-8", 
        "978-3-540-74450-4"
      ], 
      "name": "Combinatorics, Algorithms, Probabilistic and Experimental Methodologies", 
      "type": "Book"
    }, 
    "name": "A Bijective Code for k-Trees with Linear Time Encoding and Decoding", 
    "pagination": "408-420", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-74450-4_37"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "bb1976445c78f67b3381b2621950d513ad359e0539ad220d2e07fde12cabe896"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1039278055"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-74450-4_37", 
      "https://app.dimensions.ai/details/publication/pub.1039278055"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T14:26", 
    "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/0000000001_0000000264/records_8669_00000267.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-540-74450-4_37"
  }
]
 

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/978-3-540-74450-4_37'

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/978-3-540-74450-4_37'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74450-4_37'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-74450-4_37'


 

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

118 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-74450-4_37 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N60cb7d8f4c784e049cab1c06132f58d6
4 schema:citation sg:pub.10.1007/11533719_27
5 sg:pub.10.1007/978-3-540-24698-5_38
6 https://doi.org/10.1016/0012-365x(71)90023-9
7 https://doi.org/10.1016/0012-365x(75)90082-5
8 https://doi.org/10.1016/0097-3165(86)90004-x
9 https://doi.org/10.1016/s0021-9800(69)80119-5
10 https://doi.org/10.1016/s0021-9800(69)80120-1
11 https://doi.org/10.1016/s0304-3975(97)00228-4
12 https://doi.org/10.1112/s002557930000245x
13 schema:datePublished 2007
14 schema:datePublishedReg 2007-01-01
15 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, 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 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 encoding and decoding algorithms running in linear time with respect to the size of the k-tree.
16 schema:editor Nf63865c7c4394a39bef8d7b509868a4d
17 schema:genre chapter
18 schema:inLanguage en
19 schema:isAccessibleForFree true
20 schema:isPartOf N84976543c6684f6dac9bf380d911bb91
21 schema:name A Bijective Code for k-Trees with Linear Time Encoding and Decoding
22 schema:pagination 408-420
23 schema:productId N341eb5dc094f436e9cc6a9ee658e1542
24 N91f4743546524d3e8e3e4b7f3e1668d3
25 Ne0fc9d07e30d4b83bb541e327a5749da
26 schema:publisher N74eab4e44fd740308b9152a5ddfa0e0e
27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039278055
28 https://doi.org/10.1007/978-3-540-74450-4_37
29 schema:sdDatePublished 2019-04-15T14:26
30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
31 schema:sdPublisher N624f65798639446fa37b0342b3bf2ab7
32 schema:url http://link.springer.com/10.1007/978-3-540-74450-4_37
33 sgo:license sg:explorer/license/
34 sgo:sdDataset chapters
35 rdf:type schema:Chapter
36 N0b8a6bc81c5b438fb99ca3b88c7c738b schema:familyName Chen
37 schema:givenName Bo
38 rdf:type schema:Person
39 N341eb5dc094f436e9cc6a9ee658e1542 schema:name doi
40 schema:value 10.1007/978-3-540-74450-4_37
41 rdf:type schema:PropertyValue
42 N53d1d2ca8745453686464e32fa77feb9 rdf:first sg:person.013526501407.57
43 rdf:rest Nd8f12171f4f04c80928eb8bb39724537
44 N60cb7d8f4c784e049cab1c06132f58d6 rdf:first sg:person.010013323122.87
45 rdf:rest N53d1d2ca8745453686464e32fa77feb9
46 N624f65798639446fa37b0342b3bf2ab7 schema:name Springer Nature - SN SciGraph project
47 rdf:type schema:Organization
48 N74eab4e44fd740308b9152a5ddfa0e0e schema:location Berlin, Heidelberg
49 schema:name Springer Berlin Heidelberg
50 rdf:type schema:Organisation
51 N84976543c6684f6dac9bf380d911bb91 schema:isbn 978-3-540-74449-8
52 978-3-540-74450-4
53 schema:name Combinatorics, Algorithms, Probabilistic and Experimental Methodologies
54 rdf:type schema:Book
55 N91f4743546524d3e8e3e4b7f3e1668d3 schema:name dimensions_id
56 schema:value pub.1039278055
57 rdf:type schema:PropertyValue
58 Nb71031c752a2445e95ac6a46b434028e schema:familyName Paterson
59 schema:givenName Mike
60 rdf:type schema:Person
61 Nb8af429a4d854e239e06db406fe7d719 rdf:first Nb71031c752a2445e95ac6a46b434028e
62 rdf:rest Nc93b5238b45647b0a8124838eac248fa
63 Nc93b5238b45647b0a8124838eac248fa rdf:first Nd71312bc4844495e8ca9d489e2ead92c
64 rdf:rest rdf:nil
65 Nd71312bc4844495e8ca9d489e2ead92c schema:familyName Zhang
66 schema:givenName Guochuan
67 rdf:type schema:Person
68 Nd8f12171f4f04c80928eb8bb39724537 rdf:first sg:person.011402427702.78
69 rdf:rest rdf:nil
70 Ne0fc9d07e30d4b83bb541e327a5749da schema:name readcube_id
71 schema:value bb1976445c78f67b3381b2621950d513ad359e0539ad220d2e07fde12cabe896
72 rdf:type schema:PropertyValue
73 Nf63865c7c4394a39bef8d7b509868a4d rdf:first N0b8a6bc81c5b438fb99ca3b88c7c738b
74 rdf:rest Nb8af429a4d854e239e06db406fe7d719
75 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
76 schema:name Information and Computing Sciences
77 rdf:type schema:DefinedTerm
78 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
79 schema:name Data Format
80 rdf:type schema:DefinedTerm
81 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
82 schema:familyName Caminiti
83 schema:givenName Saverio
84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
85 rdf:type schema:Person
86 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
87 schema:familyName Petreschi
88 schema:givenName Rossella
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
90 rdf:type schema:Person
91 sg:person.013526501407.57 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
92 schema:familyName Fusco
93 schema:givenName Emanuele G.
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013526501407.57
95 rdf:type schema:Person
96 sg:pub.10.1007/11533719_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047625411
97 https://doi.org/10.1007/11533719_27
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-540-24698-5_38 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043716409
100 https://doi.org/10.1007/978-3-540-24698-5_38
101 rdf:type schema:CreativeWork
102 https://doi.org/10.1016/0012-365x(71)90023-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037464722
103 rdf:type schema:CreativeWork
104 https://doi.org/10.1016/0012-365x(75)90082-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032770863
105 rdf:type schema:CreativeWork
106 https://doi.org/10.1016/0097-3165(86)90004-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1038613771
107 rdf:type schema:CreativeWork
108 https://doi.org/10.1016/s0021-9800(69)80119-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044576158
109 rdf:type schema:CreativeWork
110 https://doi.org/10.1016/s0021-9800(69)80120-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044470945
111 rdf:type schema:CreativeWork
112 https://doi.org/10.1016/s0304-3975(97)00228-4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051091799
113 rdf:type schema:CreativeWork
114 https://doi.org/10.1112/s002557930000245x schema:sameAs https://app.dimensions.ai/details/publication/pub.1062055384
115 rdf:type schema:CreativeWork
116 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
117 schema:name Computer Science Department, University of Rome “La Sapienza”, via Salaria, 113-00198 Rome, Italy
118 rdf:type schema:Organization
 




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


...