A General Approach to L(h,k)-Label Interconnection Networks View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2008-07

AUTHORS

Tiziana Calamoneri, Saverio Caminiti, Rossella Petreschi

ABSTRACT

Given two non-negative integers h and k, an L(h, k)-labeling of a graph G = (V, E) is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L(h, k)-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Bene·s, CCC, Trivalent Cayley networks, are all characterized by a similar structure: they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called (l × n)-multistage graphs, containing the most common interconnection topologies, on which we study the L(h, k)-labeling. A general algorithm for L(h, k)-labeling these graphs is presented, and from this method an efficient L(2, 1)-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach. More... »

PAGES

652-659

References to SciGraph publications

  • 1999. Frequency Assignment Problems in HANDBOOK OF COMBINATORIAL OPTIMIZATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11390-008-9161-8

    DOI

    http://dx.doi.org/10.1007/s11390-008-9161-8

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "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, Sapienza University of Rome, 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, Sapienza University of Rome, 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": [
                "Department of Computer Science, Sapienza University of Rome, 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.1145/358645.358660", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010223097"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/(sici)1097-0118(199812)29:4<263::aid-jgt5>3.0.co;2-v", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1011838645"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4757-3023-4_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015892325", 
              "https://doi.org/10.1007/978-1-4757-3023-4_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jpdc.2003.09.003", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016109255"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0012-365x(02)00750-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025039317"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0012-365x(02)00750-1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025039317"
            ], 
            "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": "https://doi.org/10.1016/j.disc.2005.04.024", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032913612"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(95)00068-n", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033159326"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0020-0190(97)00027-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038409348"
            ], 
            "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.1109/proc.1980.11899", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061444670"
            ], 
            "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/s0895480100367950", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882531"
            ], 
            "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/s0895480192242821", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882897"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480193245339", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062882908"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/s0895480199351859", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062883151"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008-07", 
        "datePublishedReg": "2008-07-01", 
        "description": "Given two non-negative integers h and k, an L(h, k)-labeling of a graph G = (V, E) is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L(h, k)-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Bene\u00b7s, CCC, Trivalent Cayley networks, are all characterized by a similar structure: they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called (l \u00d7 n)-multistage graphs, containing the most common interconnection topologies, on which we study the L(h, k)-labeling. A general algorithm for L(h, k)-labeling these graphs is presented, and from this method an efficient L(2, 1)-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s11390-008-9161-8", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1320078", 
            "issn": [
              "1666-6046", 
              "1666-6038"
            ], 
            "name": "Journal of Computer Science and Technology", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "4", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "23"
          }
        ], 
        "name": "A General Approach to L(h,k)-Label Interconnection Networks", 
        "pagination": "652-659", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "5e8c3c5a2bc15365002e22e54a37d9ff83174a61b3bc0e9c6e5b7b9081564d8b"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11390-008-9161-8"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1019844018"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11390-008-9161-8", 
          "https://app.dimensions.ai/details/publication/pub.1019844018"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T13:19", 
        "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_8659_00000521.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs11390-008-9161-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/s11390-008-9161-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/s11390-008-9161-8'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11390-008-9161-8'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11390-008-9161-8'


     

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

    130 TRIPLES      21 PREDICATES      45 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11390-008-9161-8 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author N65613a4bea9543eba6648238e17c0529
    4 schema:citation sg:pub.10.1007/978-1-4757-3023-4_6
    5 https://doi.org/10.1002/(sici)1097-0118(199812)29:4<263::aid-jgt5>3.0.co;2-v
    6 https://doi.org/10.1016/0020-0190(95)00068-n
    7 https://doi.org/10.1016/j.dam.2006.03.036
    8 https://doi.org/10.1016/j.disc.2005.04.024
    9 https://doi.org/10.1016/j.jpdc.2003.09.003
    10 https://doi.org/10.1016/j.jpdc.2003.11.005
    11 https://doi.org/10.1016/s0012-365x(02)00750-1
    12 https://doi.org/10.1016/s0020-0190(97)00027-6
    13 https://doi.org/10.1093/comjnl/bxl018
    14 https://doi.org/10.1109/proc.1980.11899
    15 https://doi.org/10.1137/0405048
    16 https://doi.org/10.1137/s0895480100367950
    17 https://doi.org/10.1137/s0895480191223178
    18 https://doi.org/10.1137/s0895480192242821
    19 https://doi.org/10.1137/s0895480193245339
    20 https://doi.org/10.1137/s0895480199351859
    21 https://doi.org/10.1145/358645.358660
    22 schema:datePublished 2008-07
    23 schema:datePublishedReg 2008-07-01
    24 schema:description Given two non-negative integers h and k, an L(h, k)-labeling of a graph G = (V, E) is a function from the set V to a set of colors, such that adjacent nodes take colors at distance at least h, and nodes at distance 2 take colors at distance at least k. The aim of the L(h, k)-labeling problem is to minimize the greatest used color. Since the decisional version of this problem is NP-complete, it is important to investigate particular classes of graphs for which the problem can be efficiently solved. It is well known that the most common interconnection topologies, such as Butterfly-like, Bene·s, CCC, Trivalent Cayley networks, are all characterized by a similar structure: they have nodes organized as a matrix and connections are divided into layers. So we naturally introduce a new class of graphs, called (l × n)-multistage graphs, containing the most common interconnection topologies, on which we study the L(h, k)-labeling. A general algorithm for L(h, k)-labeling these graphs is presented, and from this method an efficient L(2, 1)-labeling for Butterfly and CCC networks is derived. Finally we describe a possible generalization of our approach.
    25 schema:genre research_article
    26 schema:inLanguage en
    27 schema:isAccessibleForFree true
    28 schema:isPartOf N0826c1d64fa548bc96ecd810f87c201d
    29 N72f422010ce44268812577419291d619
    30 sg:journal.1320078
    31 schema:name A General Approach to L(h,k)-Label Interconnection Networks
    32 schema:pagination 652-659
    33 schema:productId N266325a0908a438ebd76c5fa78a0e711
    34 N675d0b8791974dd8b62c0c2991c81af3
    35 Nddf9d3f96e1847f3aa98c4e710fad606
    36 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019844018
    37 https://doi.org/10.1007/s11390-008-9161-8
    38 schema:sdDatePublished 2019-04-10T13:19
    39 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    40 schema:sdPublisher N0a6f13e13268421cac128e3c11f2b10a
    41 schema:url http://link.springer.com/10.1007%2Fs11390-008-9161-8
    42 sgo:license sg:explorer/license/
    43 sgo:sdDataset articles
    44 rdf:type schema:ScholarlyArticle
    45 N0826c1d64fa548bc96ecd810f87c201d schema:volumeNumber 23
    46 rdf:type schema:PublicationVolume
    47 N0a6f13e13268421cac128e3c11f2b10a schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 N158fdbd014134f44852073576755d740 rdf:first sg:person.010013323122.87
    50 rdf:rest N34d04e83c895414098643626466fc4a0
    51 N266325a0908a438ebd76c5fa78a0e711 schema:name doi
    52 schema:value 10.1007/s11390-008-9161-8
    53 rdf:type schema:PropertyValue
    54 N34d04e83c895414098643626466fc4a0 rdf:first sg:person.011402427702.78
    55 rdf:rest rdf:nil
    56 N65613a4bea9543eba6648238e17c0529 rdf:first sg:person.013577775161.22
    57 rdf:rest N158fdbd014134f44852073576755d740
    58 N675d0b8791974dd8b62c0c2991c81af3 schema:name dimensions_id
    59 schema:value pub.1019844018
    60 rdf:type schema:PropertyValue
    61 N72f422010ce44268812577419291d619 schema:issueNumber 4
    62 rdf:type schema:PublicationIssue
    63 Nddf9d3f96e1847f3aa98c4e710fad606 schema:name readcube_id
    64 schema:value 5e8c3c5a2bc15365002e22e54a37d9ff83174a61b3bc0e9c6e5b7b9081564d8b
    65 rdf:type schema:PropertyValue
    66 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Information and Computing Sciences
    68 rdf:type schema:DefinedTerm
    69 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    70 schema:name Information Systems
    71 rdf:type schema:DefinedTerm
    72 sg:journal.1320078 schema:issn 1666-6038
    73 1666-6046
    74 schema:name Journal of Computer Science and Technology
    75 rdf:type schema:Periodical
    76 sg:person.010013323122.87 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    77 schema:familyName Caminiti
    78 schema:givenName Saverio
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010013323122.87
    80 rdf:type schema:Person
    81 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    82 schema:familyName Petreschi
    83 schema:givenName Rossella
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    85 rdf:type schema:Person
    86 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    87 schema:familyName Calamoneri
    88 schema:givenName Tiziana
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
    90 rdf:type schema:Person
    91 sg:pub.10.1007/978-1-4757-3023-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015892325
    92 https://doi.org/10.1007/978-1-4757-3023-4_6
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1002/(sici)1097-0118(199812)29:4<263::aid-jgt5>3.0.co;2-v schema:sameAs https://app.dimensions.ai/details/publication/pub.1011838645
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1016/0020-0190(95)00068-n schema:sameAs https://app.dimensions.ai/details/publication/pub.1033159326
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/j.dam.2006.03.036 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048103103
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/j.disc.2005.04.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032913612
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/j.jpdc.2003.09.003 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016109255
    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.1016/s0012-365x(02)00750-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025039317
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1016/s0020-0190(97)00027-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038409348
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1093/comjnl/bxl018 schema:sameAs https://app.dimensions.ai/details/publication/pub.1059479744
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1109/proc.1980.11899 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061444670
    113 rdf:type schema:CreativeWork
    114 https://doi.org/10.1137/0405048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844742
    115 rdf:type schema:CreativeWork
    116 https://doi.org/10.1137/s0895480100367950 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882531
    117 rdf:type schema:CreativeWork
    118 https://doi.org/10.1137/s0895480191223178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882846
    119 rdf:type schema:CreativeWork
    120 https://doi.org/10.1137/s0895480192242821 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882897
    121 rdf:type schema:CreativeWork
    122 https://doi.org/10.1137/s0895480193245339 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882908
    123 rdf:type schema:CreativeWork
    124 https://doi.org/10.1137/s0895480199351859 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062883151
    125 rdf:type schema:CreativeWork
    126 https://doi.org/10.1145/358645.358660 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010223097
    127 rdf:type schema:CreativeWork
    128 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    129 schema:name Department of Computer Science, Sapienza University of Rome, Rome, Italy
    130 rdf:type schema:Organization
     




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


    ...