L(2,1)-Labeling of Unigraphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2011

AUTHORS

Tiziana Calamoneri , Rossella Petreschi

ABSTRACT

The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ...,λ to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize λ and it is in general NP-complete. In this paper the problem of L(2,1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2,1)-labeling unigraphs is designed. This algorithm runs in O(n) time, improving the time of the algorithm based on the greedy technique, requiring O(m) time, that may be near to Θ(n2) for unigraphs. More... »

PAGES

57-68

References to SciGraph publications

  • 2000. λ-Coloring of Graphs in STACS 2000
  • 1999. Fixed-Parameter Complexity of λ-Labelings in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • 2009. Recognition of Unigraphs through Superposition of Graphs (Extended Abstract) in WALCOM: ALGORITHMS AND COMPUTATION
  • Book

    TITLE

    Theory and Practice of Algorithms in (Computer) Systems

    ISBN

    978-3-642-19753-6
    978-3-642-19754-3

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-19754-3_8

    DOI

    http://dx.doi.org/10.1007/978-3-642-19754-3_8

    DIMENSIONS

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


    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/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "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": [
                "Department of Computer Science, \u201cSapienza\u201d University of Rome, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Calamoneri", 
            "givenName": "Tiziana", 
            "id": "sg:person.013577775161.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Department of Computer Science, \u201cSapienza\u201d University of 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": "sg:pub.10.1007/978-3-642-00202-1_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003057903", 
              "https://doi.org/10.1007/978-3-642-00202-1_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00202-1_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003057903", 
              "https://doi.org/10.1007/978-3-642-00202-1_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46784-x_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003241800", 
              "https://doi.org/10.1007/3-540-46784-x_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2009.02.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003894476"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jpdc.2003.11.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026493116"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46541-3_33", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030934197", 
              "https://doi.org/10.1007/3-540-46541-3_33"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0095-8956(75)90072-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038496111"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/net.20257", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045604027"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.dam.2006.03.036", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048103103"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1093/comjnl/bxl018", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1059479744"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0405048", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062844742"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480191223178", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882846"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480193245339", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882908"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2011", 
        "datePublishedReg": "2011-01-01", 
        "description": "The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ...,\u03bb to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize \u03bb and it is in general NP-complete. In this paper the problem of L(2,1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2,1)-labeling unigraphs is designed. This algorithm runs in O(n) time, improving the time of the algorithm based on the greedy technique, requiring O(m) time, that may be near to \u0398(n2) for unigraphs.", 
        "editor": [
          {
            "familyName": "Marchetti-Spaccamela", 
            "givenName": "Alberto", 
            "type": "Person"
          }, 
          {
            "familyName": "Segal", 
            "givenName": "Michael", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-19754-3_8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-19753-6", 
            "978-3-642-19754-3"
          ], 
          "name": "Theory and Practice of Algorithms in (Computer) Systems", 
          "type": "Book"
        }, 
        "name": "L(2,1)-Labeling of Unigraphs", 
        "pagination": "57-68", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1029576900"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-19754-3_8"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "8ce63baad12316e755c909a959b323ba5549f716d82ebcf6bfb3fdca8fd97dfc"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-19754-3_8", 
          "https://app.dimensions.ai/details/publication/pub.1029576900"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:36", 
        "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_71680_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-19754-3_8"
      }
    ]
     

    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-642-19754-3_8'

    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-642-19754-3_8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-19754-3_8'

    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-642-19754-3_8'


     

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

    116 TRIPLES      23 PREDICATES      39 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-19754-3_8 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N65ec3182904643548e0bfc96eca069bf
    4 schema:citation sg:pub.10.1007/3-540-46541-3_33
    5 sg:pub.10.1007/3-540-46784-x_33
    6 sg:pub.10.1007/978-3-642-00202-1_15
    7 https://doi.org/10.1002/net.20257
    8 https://doi.org/10.1016/0095-8956(75)90072-6
    9 https://doi.org/10.1016/j.dam.2006.03.036
    10 https://doi.org/10.1016/j.dam.2009.02.004
    11 https://doi.org/10.1016/j.jpdc.2003.11.005
    12 https://doi.org/10.1093/comjnl/bxl018
    13 https://doi.org/10.1137/0405048
    14 https://doi.org/10.1137/s0895480191223178
    15 https://doi.org/10.1137/s0895480193245339
    16 schema:datePublished 2011
    17 schema:datePublishedReg 2011-01-01
    18 schema:description The L(2,1)-labeling problem consists of assigning colors from the integer set 0, ...,λ to the nodes of a graph G in such a way that nodes at a distance of at most two get different colors, while adjacent nodes get colors which are at least two apart. The aim of this problem is to minimize λ and it is in general NP-complete. In this paper the problem of L(2,1)-labeling unigraphs, i.e. graphs uniquely determined by their own degree sequence up to isomorphism, is addressed and a 3/2-approximate algorithm for L(2,1)-labeling unigraphs is designed. This algorithm runs in O(n) time, improving the time of the algorithm based on the greedy technique, requiring O(m) time, that may be near to Θ(n2) for unigraphs.
    19 schema:editor N8e6ed61f3c244050baaa868da0e1e792
    20 schema:genre chapter
    21 schema:inLanguage en
    22 schema:isAccessibleForFree false
    23 schema:isPartOf N6db56a09b1af4dd69048558618f2e084
    24 schema:name L(2,1)-Labeling of Unigraphs
    25 schema:pagination 57-68
    26 schema:productId N0e6da3f5ee874a6fbe5b15193d2aad9b
    27 N4512c410f5cf48c1b60b057c2d5415e2
    28 N6b4d042280a547e9812642924933bb41
    29 schema:publisher N26d544126dd64a99a4e6ed07d870a3fb
    30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029576900
    31 https://doi.org/10.1007/978-3-642-19754-3_8
    32 schema:sdDatePublished 2019-04-16T08:36
    33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    34 schema:sdPublisher Ne45f50d8df524b32a463b8ceb3d78698
    35 schema:url https://link.springer.com/10.1007%2F978-3-642-19754-3_8
    36 sgo:license sg:explorer/license/
    37 sgo:sdDataset chapters
    38 rdf:type schema:Chapter
    39 N0e6da3f5ee874a6fbe5b15193d2aad9b schema:name readcube_id
    40 schema:value 8ce63baad12316e755c909a959b323ba5549f716d82ebcf6bfb3fdca8fd97dfc
    41 rdf:type schema:PropertyValue
    42 N242110bc9d5f4352a5ebe284a673baa6 rdf:first sg:person.011402427702.78
    43 rdf:rest rdf:nil
    44 N26d544126dd64a99a4e6ed07d870a3fb schema:location Berlin, Heidelberg
    45 schema:name Springer Berlin Heidelberg
    46 rdf:type schema:Organisation
    47 N4512c410f5cf48c1b60b057c2d5415e2 schema:name dimensions_id
    48 schema:value pub.1029576900
    49 rdf:type schema:PropertyValue
    50 N4f6e396ba8b04b2292ec20c1df43d5fe schema:familyName Marchetti-Spaccamela
    51 schema:givenName Alberto
    52 rdf:type schema:Person
    53 N65ec3182904643548e0bfc96eca069bf rdf:first sg:person.013577775161.22
    54 rdf:rest N242110bc9d5f4352a5ebe284a673baa6
    55 N6b4d042280a547e9812642924933bb41 schema:name doi
    56 schema:value 10.1007/978-3-642-19754-3_8
    57 rdf:type schema:PropertyValue
    58 N6db56a09b1af4dd69048558618f2e084 schema:isbn 978-3-642-19753-6
    59 978-3-642-19754-3
    60 schema:name Theory and Practice of Algorithms in (Computer) Systems
    61 rdf:type schema:Book
    62 N89cf58ce052f4d4d8b4bc0262a99531c schema:familyName Segal
    63 schema:givenName Michael
    64 rdf:type schema:Person
    65 N8e6ed61f3c244050baaa868da0e1e792 rdf:first N4f6e396ba8b04b2292ec20c1df43d5fe
    66 rdf:rest Nc8faa68f18024a7680cd13c54174b967
    67 Nc8faa68f18024a7680cd13c54174b967 rdf:first N89cf58ce052f4d4d8b4bc0262a99531c
    68 rdf:rest rdf:nil
    69 Ne45f50d8df524b32a463b8ceb3d78698 schema:name Springer Nature - SN SciGraph project
    70 rdf:type schema:Organization
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Computation Theory and Mathematics
    76 rdf:type schema:DefinedTerm
    77 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    78 schema:familyName Petreschi
    79 schema:givenName Rossella
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    81 rdf:type schema:Person
    82 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    83 schema:familyName Calamoneri
    84 schema:givenName Tiziana
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
    86 rdf:type schema:Person
    87 sg:pub.10.1007/3-540-46541-3_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030934197
    88 https://doi.org/10.1007/3-540-46541-3_33
    89 rdf:type schema:CreativeWork
    90 sg:pub.10.1007/3-540-46784-x_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003241800
    91 https://doi.org/10.1007/3-540-46784-x_33
    92 rdf:type schema:CreativeWork
    93 sg:pub.10.1007/978-3-642-00202-1_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003057903
    94 https://doi.org/10.1007/978-3-642-00202-1_15
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1002/net.20257 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045604027
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0095-8956(75)90072-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038496111
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/j.dam.2006.03.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048103103
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/j.dam.2009.02.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003894476
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/j.jpdc.2003.11.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026493116
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1093/comjnl/bxl018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059479744
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1137/0405048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844742
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1137/s0895480191223178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882846
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1137/s0895480193245339 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882908
    113 rdf:type schema:CreativeWork
    114 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    115 schema:name Department of Computer Science, “Sapienza” University of Rome, Italy
    116 rdf:type schema:Organization
     




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


    ...