A Unified Approach to Coding Labeled Trees View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2004

AUTHORS

Saverio Caminiti , Irene Finocchi , Rossella Petreschi

ABSTRACT

We consider the problem of coding labeled trees by means of strings of node labels and we present a unified approach based on a reduction of both coding and decoding to integer (radix) sorting. Applying this approach to four well-known codes introduced by Prüfer [18], Neville [17], and Deo and Micikevicius [5], we close some open problems. With respect to coding, our general sequential algorithm requires optimal linear time, thus solving the problem of optimally computing the second code presented by Neville. The algorithm can be parallelized on the EREW PRAM model, so as to work in O(logn) time using O(n) or operations, depending on the code. With respect to decoding, the problem of finding an optimal sequential algorithm for the second Neville code was also open, and our general scheme solves it. Furthermore, in a parallel setting our scheme yields the first efficient decoding algorithms for the codes in [5] and [17]. More... »

PAGES

339-348

References to SciGraph publications

Book

TITLE

LATIN 2004: Theoretical Informatics

ISBN

978-3-540-21258-4
978-3-540-24698-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-24698-5_38

DOI

http://dx.doi.org/10.1007/978-3-540-24698-5_38

DIMENSIONS

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


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": [
            "DSI, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Roma, 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": "University of Rome Tor Vergata", 
          "id": "https://www.grid.ac/institutes/grid.6530.0", 
          "name": [
            "DISP, Universit\u00e0 degli Studi di Roma \u201cTor Vergata\u201d, Via del Politecnico 1, 00133, Roma, Italy"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Finocchi", 
        "givenName": "Irene", 
        "id": "sg:person.014240412541.72", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Sapienza University of Rome", 
          "id": "https://www.grid.ac/institutes/grid.7841.a", 
          "name": [
            "DSI, Universit\u00e0 degli Studi di Roma \u201cLa Sapienza\u201d, Via Salaria 113, 00198, Roma, 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/s0166-218x(99)00221-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006258311"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1002/(sici)1097-0037(199709)30:2<91::aid-net3>3.0.co;2-f", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013908963"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s002249910006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1037393494", 
          "https://doi.org/10.1007/s002249910006"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1080/10637199408915406", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1043032053"
        ], 
        "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.1109/71.640015", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1061217695"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/0218035", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062842134"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1137/s0097539799352449", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062880316"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "We consider the problem of coding labeled trees by means of strings of node labels and we present a unified approach based on a reduction of both coding and decoding to integer (radix) sorting. Applying this approach to four well-known codes introduced by Pr\u00fcfer [18], Neville [17], and Deo and Micikevicius [5], we close some open problems. With respect to coding, our general sequential algorithm requires optimal linear time, thus solving the problem of optimally computing the second code presented by Neville. The algorithm can be parallelized on the EREW PRAM model, so as to work in O(logn) time using O(n) or operations, depending on the code. With respect to decoding, the problem of finding an optimal sequential algorithm for the second Neville code was also open, and our general scheme solves it. Furthermore, in a parallel setting our scheme yields the first efficient decoding algorithms for the codes in [5] and [17].", 
    "editor": [
      {
        "familyName": "Farach-Colton", 
        "givenName": "Mart\u00edn", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-24698-5_38", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-21258-4", 
        "978-3-540-24698-5"
      ], 
      "name": "LATIN 2004: Theoretical Informatics", 
      "type": "Book"
    }, 
    "name": "A Unified Approach to Coding Labeled Trees", 
    "pagination": "339-348", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1043716409"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-24698-5_38"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "d03cd6739a91d464f1b2db18e3a5b6ded9c809f7ef745d035e74fbf2103c4e11"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-24698-5_38", 
      "https://app.dimensions.ai/details/publication/pub.1043716409"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T08:37", 
    "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/0000000365_0000000365/records_71689_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F978-3-540-24698-5_38"
  }
]
 

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-24698-5_38'

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-24698-5_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-24698-5_38'

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-24698-5_38'


 

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

107 TRIPLES      23 PREDICATES      35 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-24698-5_38 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N659226ca9e76459684f100d46c6f671c
4 schema:citation sg:pub.10.1007/s002249910006
5 https://doi.org/10.1002/(sici)1097-0037(199709)30:2<91::aid-net3>3.0.co;2-f
6 https://doi.org/10.1016/s0166-218x(99)00221-8
7 https://doi.org/10.1017/s030500410002853x
8 https://doi.org/10.1080/10637199408915406
9 https://doi.org/10.1109/71.640015
10 https://doi.org/10.1137/0218035
11 https://doi.org/10.1137/s0097539799352449
12 schema:datePublished 2004
13 schema:datePublishedReg 2004-01-01
14 schema:description We consider the problem of coding labeled trees by means of strings of node labels and we present a unified approach based on a reduction of both coding and decoding to integer (radix) sorting. Applying this approach to four well-known codes introduced by Prüfer [18], Neville [17], and Deo and Micikevicius [5], we close some open problems. With respect to coding, our general sequential algorithm requires optimal linear time, thus solving the problem of optimally computing the second code presented by Neville. The algorithm can be parallelized on the EREW PRAM model, so as to work in O(logn) time using O(n) or operations, depending on the code. With respect to decoding, the problem of finding an optimal sequential algorithm for the second Neville code was also open, and our general scheme solves it. Furthermore, in a parallel setting our scheme yields the first efficient decoding algorithms for the codes in [5] and [17].
15 schema:editor Ndca8733b94ee408c95a8e61d20bcbc99
16 schema:genre chapter
17 schema:inLanguage en
18 schema:isAccessibleForFree true
19 schema:isPartOf Nc9075d91d7694067afaae8a51851ceaf
20 schema:name A Unified Approach to Coding Labeled Trees
21 schema:pagination 339-348
22 schema:productId N3c8f470c814644f3b416450fa760ef1f
23 Nb3812667a00340db88d719d349ecd4a1
24 Ndfccee3eaead449aba3a9212e5e57cdb
25 schema:publisher Na5a53b25dee94977a818e2a0892366d1
26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043716409
27 https://doi.org/10.1007/978-3-540-24698-5_38
28 schema:sdDatePublished 2019-04-16T08:37
29 schema:sdLicense https://scigraph.springernature.com/explorer/license/
30 schema:sdPublisher N073b05a6002a4ab9aa0ce3bb7164103d
31 schema:url https://link.springer.com/10.1007%2F978-3-540-24698-5_38
32 sgo:license sg:explorer/license/
33 sgo:sdDataset chapters
34 rdf:type schema:Chapter
35 N073b05a6002a4ab9aa0ce3bb7164103d schema:name Springer Nature - SN SciGraph project
36 rdf:type schema:Organization
37 N3c8f470c814644f3b416450fa760ef1f schema:name doi
38 schema:value 10.1007/978-3-540-24698-5_38
39 rdf:type schema:PropertyValue
40 N5f1392a00c4d4199a595214d9cb5f6f4 rdf:first sg:person.011402427702.78
41 rdf:rest rdf:nil
42 N659226ca9e76459684f100d46c6f671c rdf:first sg:person.010013323122.87
43 rdf:rest N85ea25b15ea849bd9ced7b3c9a6ccf2e
44 N85ea25b15ea849bd9ced7b3c9a6ccf2e rdf:first sg:person.014240412541.72
45 rdf:rest N5f1392a00c4d4199a595214d9cb5f6f4
46 Na5a53b25dee94977a818e2a0892366d1 schema:location Berlin, Heidelberg
47 schema:name Springer Berlin Heidelberg
48 rdf:type schema:Organisation
49 Nb3812667a00340db88d719d349ecd4a1 schema:name readcube_id
50 schema:value d03cd6739a91d464f1b2db18e3a5b6ded9c809f7ef745d035e74fbf2103c4e11
51 rdf:type schema:PropertyValue
52 Nc9075d91d7694067afaae8a51851ceaf schema:isbn 978-3-540-21258-4
53 978-3-540-24698-5
54 schema:name LATIN 2004: Theoretical Informatics
55 rdf:type schema:Book
56 Ndca8733b94ee408c95a8e61d20bcbc99 rdf:first Ne2a214b74daf4083aa8762c148a9ec0d
57 rdf:rest rdf:nil
58 Ndfccee3eaead449aba3a9212e5e57cdb schema:name dimensions_id
59 schema:value pub.1043716409
60 rdf:type schema:PropertyValue
61 Ne2a214b74daf4083aa8762c148a9ec0d schema:familyName Farach-Colton
62 schema:givenName Martín
63 rdf:type schema:Person
64 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
65 schema:name Information and Computing Sciences
66 rdf:type schema:DefinedTerm
67 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
68 schema:name Data Format
69 rdf:type schema:DefinedTerm
70 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
71 schema:familyName Caminiti
72 schema:givenName Saverio
73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
74 rdf:type schema:Person
75 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
76 schema:familyName Petreschi
77 schema:givenName Rossella
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
79 rdf:type schema:Person
80 sg:person.014240412541.72 schema:affiliation https://www.grid.ac/institutes/grid.6530.0
81 schema:familyName Finocchi
82 schema:givenName Irene
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014240412541.72
84 rdf:type schema:Person
85 sg:pub.10.1007/s002249910006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037393494
86 https://doi.org/10.1007/s002249910006
87 rdf:type schema:CreativeWork
88 https://doi.org/10.1002/(sici)1097-0037(199709)30:2<91::aid-net3>3.0.co;2-f schema:sameAs https://app.dimensions.ai/details/publication/pub.1013908963
89 rdf:type schema:CreativeWork
90 https://doi.org/10.1016/s0166-218x(99)00221-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006258311
91 rdf:type schema:CreativeWork
92 https://doi.org/10.1017/s030500410002853x schema:sameAs https://app.dimensions.ai/details/publication/pub.1054084145
93 rdf:type schema:CreativeWork
94 https://doi.org/10.1080/10637199408915406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043032053
95 rdf:type schema:CreativeWork
96 https://doi.org/10.1109/71.640015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061217695
97 rdf:type schema:CreativeWork
98 https://doi.org/10.1137/0218035 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062842134
99 rdf:type schema:CreativeWork
100 https://doi.org/10.1137/s0097539799352449 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062880316
101 rdf:type schema:CreativeWork
102 https://www.grid.ac/institutes/grid.6530.0 schema:alternateName University of Rome Tor Vergata
103 schema:name DISP, Università degli Studi di Roma “Tor Vergata”, Via del Politecnico 1, 00133, Roma, Italy
104 rdf:type schema:Organization
105 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
106 schema:name DSI, Università degli Studi di Roma “La Sapienza”, Via Salaria 113, 00198, Roma, Italy
107 rdf:type schema:Organization
 




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


...