L(2, 1)-Coloring Matrogenic Graphs View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

AUTHORS

Tiziana Calamoneri , Rossella Petreschi

ABSTRACT

This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In this problem, channels assigned to adjacent vertices must be at least two apart, while the same channel can be reused for vertices whose distance is at least three. Linear time algorithms are provided for matrogenic graphs and, in particular, for two specific subclasses: threshold graphs and split matrogenic graphs. For the first one of these classes the algorithm is exact, while for the other ones it approximates the optimal solution. Consequently, improvements on previously known results concerning subclasses of cographs, split graphs and graphs with diameter two are achieved. More... »

PAGES

236-247

References to SciGraph publications

  • 1999. Fixed-Parameter Complexity of λ-Labelings in GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE
  • Book

    TITLE

    LATIN 2002: Theoretical Informatics

    ISBN

    978-3-540-43400-9
    978-3-540-45995-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45995-2_24

    DOI

    http://dx.doi.org/10.1007/3-540-45995-2_24

    DIMENSIONS

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


    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, University of Rome \u201cLa Sapienza\u201d - Italy, via Salaria 113, 00198\u00a0Roma, 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, University of Rome \u201cLa Sapienza\u201d - Italy, via Salaria 113, 00198\u00a0Roma, 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(84)90023-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001514301"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0012-365x(99)00400-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002643745"
            ], 
            "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.1145/381448.381452", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004096330"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0167-5060(08)70731-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1046754752"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0206008", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062841347"
            ], 
            "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": "2002", 
        "datePublishedReg": "2002-01-01", 
        "description": "This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In this problem, channels assigned to adjacent vertices must be at least two apart, while the same channel can be reused for vertices whose distance is at least three. Linear time algorithms are provided for matrogenic graphs and, in particular, for two specific subclasses: threshold graphs and split matrogenic graphs. For the first one of these classes the algorithm is exact, while for the other ones it approximates the optimal solution. Consequently, improvements on previously known results concerning subclasses of cographs, split graphs and graphs with diameter two are achieved.", 
        "editor": [
          {
            "familyName": "Rajsbaum", 
            "givenName": "Sergio", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45995-2_24", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-43400-9", 
            "978-3-540-45995-8"
          ], 
          "name": "LATIN 2002: Theoretical Informatics", 
          "type": "Book"
        }, 
        "name": "L(2, 1)-Coloring Matrogenic Graphs", 
        "pagination": "236-247", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45995-2_24"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "9fa4346c126e924e68b710061d9f454fbd29c86d708378e78b673f1eed4887a6"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1033511711"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45995-2_24", 
          "https://app.dimensions.ai/details/publication/pub.1033511711"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T21:03", 
        "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_8690_00000264.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45995-2_24"
      }
    ]
     

    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/3-540-45995-2_24'

    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/3-540-45995-2_24'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45995-2_24'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-45995-2_24'


     

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

    100 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45995-2_24 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N4ec4e576424f4577a0a9757da1d5c0f8
    4 schema:citation sg:pub.10.1007/3-540-46784-x_33
    5 https://doi.org/10.1016/0012-365x(84)90023-2
    6 https://doi.org/10.1016/s0012-365x(99)00400-8
    7 https://doi.org/10.1016/s0167-5060(08)70731-3
    8 https://doi.org/10.1137/0206008
    9 https://doi.org/10.1137/0405048
    10 https://doi.org/10.1137/s0895480191223178
    11 https://doi.org/10.1137/s0895480193245339
    12 https://doi.org/10.1145/381448.381452
    13 schema:datePublished 2002
    14 schema:datePublishedReg 2002-01-01
    15 schema:description This paper investigates a variant of the general problem of assigning channels to the stations of a wireless network when the graph representing the possible interferences is a matrogenic graph. In this problem, channels assigned to adjacent vertices must be at least two apart, while the same channel can be reused for vertices whose distance is at least three. Linear time algorithms are provided for matrogenic graphs and, in particular, for two specific subclasses: threshold graphs and split matrogenic graphs. For the first one of these classes the algorithm is exact, while for the other ones it approximates the optimal solution. Consequently, improvements on previously known results concerning subclasses of cographs, split graphs and graphs with diameter two are achieved.
    16 schema:editor Nf7e0b948550e431bbfb2f261c047506b
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf N7cd9f73eb7f94180ad527dc5e89b58f6
    21 schema:name L(2, 1)-Coloring Matrogenic Graphs
    22 schema:pagination 236-247
    23 schema:productId N1676a4c03c784e179556814afc703047
    24 N83a362fd00664996a13667020c5adddc
    25 Na8e0fda2c46d4a5fa9cb317dd78f1f02
    26 schema:publisher N621d6f4e09ee4923b5b5bfcdbf48fcab
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033511711
    28 https://doi.org/10.1007/3-540-45995-2_24
    29 schema:sdDatePublished 2019-04-15T21:03
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N15bbb489eb614716871b4c62cfc4491a
    32 schema:url http://link.springer.com/10.1007/3-540-45995-2_24
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N15bbb489eb614716871b4c62cfc4491a schema:name Springer Nature - SN SciGraph project
    37 rdf:type schema:Organization
    38 N1676a4c03c784e179556814afc703047 schema:name readcube_id
    39 schema:value 9fa4346c126e924e68b710061d9f454fbd29c86d708378e78b673f1eed4887a6
    40 rdf:type schema:PropertyValue
    41 N4ec4e576424f4577a0a9757da1d5c0f8 rdf:first sg:person.013577775161.22
    42 rdf:rest N95882cdadff04dceac409095471fbf25
    43 N621d6f4e09ee4923b5b5bfcdbf48fcab schema:location Berlin, Heidelberg
    44 schema:name Springer Berlin Heidelberg
    45 rdf:type schema:Organisation
    46 N7cd9f73eb7f94180ad527dc5e89b58f6 schema:isbn 978-3-540-43400-9
    47 978-3-540-45995-8
    48 schema:name LATIN 2002: Theoretical Informatics
    49 rdf:type schema:Book
    50 N83a362fd00664996a13667020c5adddc schema:name doi
    51 schema:value 10.1007/3-540-45995-2_24
    52 rdf:type schema:PropertyValue
    53 N95882cdadff04dceac409095471fbf25 rdf:first sg:person.011402427702.78
    54 rdf:rest rdf:nil
    55 Na8e0fda2c46d4a5fa9cb317dd78f1f02 schema:name dimensions_id
    56 schema:value pub.1033511711
    57 rdf:type schema:PropertyValue
    58 Nb618b1cebeee4a548ef54a83a030ebfb schema:familyName Rajsbaum
    59 schema:givenName Sergio
    60 rdf:type schema:Person
    61 Nf7e0b948550e431bbfb2f261c047506b rdf:first Nb618b1cebeee4a548ef54a83a030ebfb
    62 rdf:rest rdf:nil
    63 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    64 schema:name Information and Computing Sciences
    65 rdf:type schema:DefinedTerm
    66 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    67 schema:name Computation Theory and Mathematics
    68 rdf:type schema:DefinedTerm
    69 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    70 schema:familyName Petreschi
    71 schema:givenName Rossella
    72 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    73 rdf:type schema:Person
    74 sg:person.013577775161.22 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    75 schema:familyName Calamoneri
    76 schema:givenName Tiziana
    77 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013577775161.22
    78 rdf:type schema:Person
    79 sg:pub.10.1007/3-540-46784-x_33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003241800
    80 https://doi.org/10.1007/3-540-46784-x_33
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/0012-365x(84)90023-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001514301
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1016/s0012-365x(99)00400-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002643745
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1016/s0167-5060(08)70731-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046754752
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1137/0206008 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062841347
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1137/0405048 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062844742
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.1137/s0895480191223178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882846
    93 rdf:type schema:CreativeWork
    94 https://doi.org/10.1137/s0895480193245339 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062882908
    95 rdf:type schema:CreativeWork
    96 https://doi.org/10.1145/381448.381452 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004096330
    97 rdf:type schema:CreativeWork
    98 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    99 schema:name Department of Computer Science, University of Rome “La Sapienza” - Italy, via Salaria 113, 00198 Roma, Italy
    100 rdf:type schema:Organization
     




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


    ...