Labeling Schemes for Tree Representation View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

Reuven Cohen , Pierre Fraigniaud , David Ilcinkas , Amos Korman , David Peleg

ABSTRACT

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted Mup(T) and Sup(T) for and Mall(T) and Sall(T) for . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,...,deg(v) – 1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for Mup(T), Sup(T) and Sall(T) but NP-hard for Mall(T) (even for 3-regular planar graphs). We show that for every graph G and port numbering there exists a spanning tree T for which Sup(T) = O(n log log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes. More... »

PAGES

13-24

References to SciGraph publications

  • 2005. Label-Guided Graph Exploration by a Finite Automaton in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1997. Bounded degree spanning trees in ALGORITHMS — ESA '97
  • Book

    TITLE

    Distributed Computing – IWDC 2005

    ISBN

    978-3-540-30959-8
    978-3-540-32428-7

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/11603771_2

    DOI

    http://dx.doi.org/10.1007/11603771_2

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Dept. of Computer Science, Weizmann Institute, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cohen", 
            "givenName": "Reuven", 
            "id": "sg:person.013647657237.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013647657237.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "CNRS, LRI, Universit\u00e9 Paris-Sud, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Fraigniaud", 
            "givenName": "Pierre", 
            "id": "sg:person.013424402135.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "French National Centre for Scientific Research", 
              "id": "https://www.grid.ac/institutes/grid.4444.0", 
              "name": [
                "CNRS, LRI, Universit\u00e9 Paris-Sud, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Ilcinkas", 
            "givenName": "David", 
            "id": "sg:person.010032333055.75", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010032333055.75"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Dept. of Computer Science, Weizmann Institute, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Korman", 
            "givenName": "Amos", 
            "id": "sg:person.013353220506.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Weizmann Institute of Science", 
              "id": "https://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Dept. of Computer Science, Weizmann Institute, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Peleg", 
            "givenName": "David", 
            "id": "sg:person.012357743251.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357743251.05"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-63397-9_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019189045", 
              "https://doi.org/10.1007/3-540-63397-9_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040407045", 
              "https://doi.org/10.1007/11523468_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11523468_28", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040407045", 
              "https://doi.org/10.1007/11523468_28"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.1975.1055349", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061647584"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0205049", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841335"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.6028/jres.071b.032", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1073599367"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/1.9780898719772", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098557268"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2005", 
        "datePublishedReg": "2005-01-01", 
        "description": "This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted Mup(T) and Sup(T) for and Mall(T) and Sall(T) for . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,...,deg(v) \u2013 1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for Mup(T), Sup(T) and Sall(T) but NP-hard for Mall(T) (even for 3-regular planar graphs). We show that for every graph G and port numbering there exists a spanning tree T for which Sup(T) = O(n log log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.", 
        "editor": [
          {
            "familyName": "Pal", 
            "givenName": "Ajit", 
            "type": "Person"
          }, 
          {
            "familyName": "Kshemkalyani", 
            "givenName": "Ajay D.", 
            "type": "Person"
          }, 
          {
            "familyName": "Kumar", 
            "givenName": "Rajeev", 
            "type": "Person"
          }, 
          {
            "familyName": "Gupta", 
            "givenName": "Arobinda", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/11603771_2", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-540-30959-8", 
            "978-3-540-32428-7"
          ], 
          "name": "Distributed Computing \u2013 IWDC 2005", 
          "type": "Book"
        }, 
        "name": "Labeling Schemes for Tree Representation", 
        "pagination": "13-24", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1014679656"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/11603771_2"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "45efed5587b2a6448e96d209f3dd5bfe858cc39c9590edb1a0108bf6b5d2c58e"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/11603771_2", 
          "https://app.dimensions.ai/details/publication/pub.1014679656"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:31", 
        "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/0000000356_0000000356/records_57889_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F11603771_2"
      }
    ]
     

    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/11603771_2'

    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/11603771_2'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11603771_2'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11603771_2'


     

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

    131 TRIPLES      23 PREDICATES      33 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/11603771_2 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author Ncb7bbd96138c40af9e6496ad6a2b1765
    4 schema:citation sg:pub.10.1007/11523468_28
    5 sg:pub.10.1007/3-540-63397-9_9
    6 https://doi.org/10.1109/tit.1975.1055349
    7 https://doi.org/10.1137/0205049
    8 https://doi.org/10.1137/1.9780898719772
    9 https://doi.org/10.6028/jres.071b.032
    10 schema:datePublished 2005
    11 schema:datePublishedReg 2005-01-01
    12 schema:description This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted Mup(T) and Sup(T) for and Mall(T) and Sall(T) for . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,...,deg(v) – 1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for Mup(T), Sup(T) and Sall(T) but NP-hard for Mall(T) (even for 3-regular planar graphs). We show that for every graph G and port numbering there exists a spanning tree T for which Sup(T) = O(n log log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port assignments. We conclude by discussing some applications for our tree representation schemes.
    13 schema:editor Naa33c41600c24972aa50f22f027cbafa
    14 schema:genre chapter
    15 schema:inLanguage en
    16 schema:isAccessibleForFree true
    17 schema:isPartOf Ncf5c99c623924e29892abdddebc001fe
    18 schema:name Labeling Schemes for Tree Representation
    19 schema:pagination 13-24
    20 schema:productId N04332329c6fc488fb81f8edf524f58f6
    21 N0ff95c7fe25f499ba6f12583e8813b3e
    22 Na6bf0c77e8804b95b45afafa062d8eaa
    23 schema:publisher Nfd7d0702e7db48539bd73f51b08e0642
    24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014679656
    25 https://doi.org/10.1007/11603771_2
    26 schema:sdDatePublished 2019-04-16T07:31
    27 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    28 schema:sdPublisher N0691e59c0a11465a976de80898f095f3
    29 schema:url https://link.springer.com/10.1007%2F11603771_2
    30 sgo:license sg:explorer/license/
    31 sgo:sdDataset chapters
    32 rdf:type schema:Chapter
    33 N04332329c6fc488fb81f8edf524f58f6 schema:name dimensions_id
    34 schema:value pub.1014679656
    35 rdf:type schema:PropertyValue
    36 N0691e59c0a11465a976de80898f095f3 schema:name Springer Nature - SN SciGraph project
    37 rdf:type schema:Organization
    38 N0ff95c7fe25f499ba6f12583e8813b3e schema:name readcube_id
    39 schema:value 45efed5587b2a6448e96d209f3dd5bfe858cc39c9590edb1a0108bf6b5d2c58e
    40 rdf:type schema:PropertyValue
    41 N2ce38cf60304412ca24839f2880d32d2 rdf:first sg:person.013424402135.28
    42 rdf:rest Nea159baa6b66401f8ae1eb48fdce2a6a
    43 N4433543942ba44908e9faab148bb78e3 rdf:first sg:person.012357743251.05
    44 rdf:rest rdf:nil
    45 N4b27b288bbd44027aa2bf63d9f59e07c schema:familyName Gupta
    46 schema:givenName Arobinda
    47 rdf:type schema:Person
    48 N4f6602c6bec546d2830f6620250048f0 schema:familyName Kshemkalyani
    49 schema:givenName Ajay D.
    50 rdf:type schema:Person
    51 N5867659daf1345d08fc8018fdc8d1f6b rdf:first N846620b99a90426b914cce8b497d5fe4
    52 rdf:rest N788e628cfc4445cbbe3b982ec310fd69
    53 N788e628cfc4445cbbe3b982ec310fd69 rdf:first N4b27b288bbd44027aa2bf63d9f59e07c
    54 rdf:rest rdf:nil
    55 N846620b99a90426b914cce8b497d5fe4 schema:familyName Kumar
    56 schema:givenName Rajeev
    57 rdf:type schema:Person
    58 N847924570df04cdba4b7332fcac07352 schema:familyName Pal
    59 schema:givenName Ajit
    60 rdf:type schema:Person
    61 Na6bf0c77e8804b95b45afafa062d8eaa schema:name doi
    62 schema:value 10.1007/11603771_2
    63 rdf:type schema:PropertyValue
    64 Naa33c41600c24972aa50f22f027cbafa rdf:first N847924570df04cdba4b7332fcac07352
    65 rdf:rest Nd457dc7e35a24f77ac94d92ae8251d41
    66 Ncb7bbd96138c40af9e6496ad6a2b1765 rdf:first sg:person.013647657237.68
    67 rdf:rest N2ce38cf60304412ca24839f2880d32d2
    68 Ncd8a7331331342989f078fa0c8b95edb rdf:first sg:person.013353220506.00
    69 rdf:rest N4433543942ba44908e9faab148bb78e3
    70 Ncf5c99c623924e29892abdddebc001fe schema:isbn 978-3-540-30959-8
    71 978-3-540-32428-7
    72 schema:name Distributed Computing – IWDC 2005
    73 rdf:type schema:Book
    74 Nd457dc7e35a24f77ac94d92ae8251d41 rdf:first N4f6602c6bec546d2830f6620250048f0
    75 rdf:rest N5867659daf1345d08fc8018fdc8d1f6b
    76 Nea159baa6b66401f8ae1eb48fdce2a6a rdf:first sg:person.010032333055.75
    77 rdf:rest Ncd8a7331331342989f078fa0c8b95edb
    78 Nfd7d0702e7db48539bd73f51b08e0642 schema:location Berlin, Heidelberg
    79 schema:name Springer Berlin Heidelberg
    80 rdf:type schema:Organisation
    81 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Mathematical Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Pure Mathematics
    86 rdf:type schema:DefinedTerm
    87 sg:person.010032333055.75 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    88 schema:familyName Ilcinkas
    89 schema:givenName David
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010032333055.75
    91 rdf:type schema:Person
    92 sg:person.012357743251.05 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    93 schema:familyName Peleg
    94 schema:givenName David
    95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012357743251.05
    96 rdf:type schema:Person
    97 sg:person.013353220506.00 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    98 schema:familyName Korman
    99 schema:givenName Amos
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013353220506.00
    101 rdf:type schema:Person
    102 sg:person.013424402135.28 schema:affiliation https://www.grid.ac/institutes/grid.4444.0
    103 schema:familyName Fraigniaud
    104 schema:givenName Pierre
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013424402135.28
    106 rdf:type schema:Person
    107 sg:person.013647657237.68 schema:affiliation https://www.grid.ac/institutes/grid.13992.30
    108 schema:familyName Cohen
    109 schema:givenName Reuven
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013647657237.68
    111 rdf:type schema:Person
    112 sg:pub.10.1007/11523468_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040407045
    113 https://doi.org/10.1007/11523468_28
    114 rdf:type schema:CreativeWork
    115 sg:pub.10.1007/3-540-63397-9_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019189045
    116 https://doi.org/10.1007/3-540-63397-9_9
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1109/tit.1975.1055349 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061647584
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1137/0205049 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841335
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1137/1.9780898719772 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098557268
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.6028/jres.071b.032 schema:sameAs https://app.dimensions.ai/details/publication/pub.1073599367
    125 rdf:type schema:CreativeWork
    126 https://www.grid.ac/institutes/grid.13992.30 schema:alternateName Weizmann Institute of Science
    127 schema:name Dept. of Computer Science, Weizmann Institute, Israel
    128 rdf:type schema:Organization
    129 https://www.grid.ac/institutes/grid.4444.0 schema:alternateName French National Centre for Scientific Research
    130 schema:name CNRS, LRI, Université Paris-Sud, France
    131 rdf:type schema:Organization
     




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


    ...