On Relaxing the Constraints in Pairwise Compatibility Graphs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Tiziana Calamoneri , Rossella Petreschi , Blerina Sinaimeri

ABSTRACT

A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d min and d max such that each leaf l u of T corresponds to a vertex u ∈ V and there is an edge (u,v) ∈ E if and only if d min ≤ d T (l u , l v ) ≤ d max where d T (l u , l v ) is the sum of the weights of the edges on the unique path from l u to l v in T. In this paper we analyze the class of PCG in relation with two particular subclasses resulting from the the cases where d min = 0 (LPG) and d max = + ∞ (mLPG). In particular, we show that the union of LPG and mLPG does not coincide with the whole class PCG, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, as the graphs we deal with belong to the more general class of split matrogenic graphs, we focus on this class of graphs for which we try to establish the membership to the PCG class. More... »

PAGES

124-135

References to SciGraph publications

  • 2009-05. Pairwise compatibility graphs in JOURNAL OF APPLIED MATHEMATICS AND COMPUTING
  • 2003. Efficient Generation of Uniform Samples from Phylogenetic Trees in ALGORITHMS IN BIOINFORMATICS
  • 2008. Leaf Powers and Their Properties: Using the Trees in ALGORITHMS AND COMPUTATION
  • Book

    TITLE

    WALCOM: Algorithms and Computation

    ISBN

    978-3-642-28075-7
    978-3-642-28076-4

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-28076-4_14

    DOI

    http://dx.doi.org/10.1007/978-3-642-28076-4_14

    DIMENSIONS

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


    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/1109", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Neurosciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/11", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Medical and Health 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, via Salaria 113, 00198\u00a0Roma"
              ], 
              "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, via Salaria 113, 00198\u00a0Roma"
              ], 
              "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"
          }, 
          {
            "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, via Salaria 113, 00198\u00a0Roma"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sinaimeri", 
            "givenName": "Blerina", 
            "id": "sg:person.01217440160.03", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01217440160.03"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-540-39763-2_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001248165", 
              "https://doi.org/10.1007/978-3-540-39763-2_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-39763-2_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1001248165", 
              "https://doi.org/10.1007/978-3-540-39763-2_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.disc.2009.10.006", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021270134"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.2001.1195", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023071535"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.ipl.2006.01.004", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023650431"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s12190-008-0204-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028947261", 
              "https://doi.org/10.1007/s12190-008-0204-7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/1435375.1435386", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034114283"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92182-0_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039610614", 
              "https://doi.org/10.1007/978-3-540-92182-0_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-92182-0_37", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039610614", 
              "https://doi.org/10.1007/978-3-540-92182-0_37"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jda.2005.06.005", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1052131278"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1142/s1793830910000917", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1063025166"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012", 
        "datePublishedReg": "2012-01-01", 
        "description": "A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d min and d max such that each leaf l u of T corresponds to a vertex u\u2009\u2208\u2009V and there is an edge (u,v)\u2009\u2208\u2009E if and only if d min \u2009\u2264\u2009d T (l u , l v )\u2009\u2264\u2009d max where d T (l u , l v ) is the sum of the weights of the edges on the unique path from l u to l v in T. In this paper we analyze the class of PCG in relation with two particular subclasses resulting from the the cases where d min \u2009=\u20090 (LPG) and d max \u2009=\u2009+\u2009\u221e (mLPG). In particular, we show that the union of LPG and mLPG does not coincide with the whole class PCG, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, as the graphs we deal with belong to the more general class of split matrogenic graphs, we focus on this class of graphs for which we try to establish the membership to the PCG class.", 
        "editor": [
          {
            "familyName": "Rahman", 
            "givenName": "Md. Saidur", 
            "type": "Person"
          }, 
          {
            "familyName": "Nakano", 
            "givenName": "Shin-ichi", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-28076-4_14", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-28075-7", 
            "978-3-642-28076-4"
          ], 
          "name": "WALCOM: Algorithms and Computation", 
          "type": "Book"
        }, 
        "name": "On Relaxing the Constraints in Pairwise Compatibility Graphs", 
        "pagination": "124-135", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-28076-4_14"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "0deb7f9e3eb5ae2a9f26d2c51019b958374b684160d9f6f618a5c4ef2f75fd44"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1002922678"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-28076-4_14", 
          "https://app.dimensions.ai/details/publication/pub.1002922678"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T17:11", 
        "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_8678_00000244.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/978-3-642-28076-4_14"
      }
    ]
     

    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-28076-4_14'

    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-28076-4_14'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-28076-4_14'

    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-28076-4_14'


     

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

    114 TRIPLES      23 PREDICATES      36 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-28076-4_14 schema:about anzsrc-for:11
    2 anzsrc-for:1109
    3 schema:author Necc8a07e3a2645c4993f585246eaf3ce
    4 schema:citation sg:pub.10.1007/978-3-540-39763-2_14
    5 sg:pub.10.1007/978-3-540-92182-0_37
    6 sg:pub.10.1007/s12190-008-0204-7
    7 https://doi.org/10.1006/jagm.2001.1195
    8 https://doi.org/10.1016/j.disc.2009.10.006
    9 https://doi.org/10.1016/j.ipl.2006.01.004
    10 https://doi.org/10.1016/j.jda.2005.06.005
    11 https://doi.org/10.1142/s1793830910000917
    12 https://doi.org/10.1145/1435375.1435386
    13 schema:datePublished 2012
    14 schema:datePublishedReg 2012-01-01
    15 schema:description A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two non-negative real numbers d min and d max such that each leaf l u of T corresponds to a vertex u ∈ V and there is an edge (u,v) ∈ E if and only if d min  ≤ d T (l u , l v ) ≤ d max where d T (l u , l v ) is the sum of the weights of the edges on the unique path from l u to l v in T. In this paper we analyze the class of PCG in relation with two particular subclasses resulting from the the cases where d min  = 0 (LPG) and d max  = + ∞ (mLPG). In particular, we show that the union of LPG and mLPG does not coincide with the whole class PCG, their intersection is not empty, and that neither of the classes LPG and mLPG is contained in the other. Finally, as the graphs we deal with belong to the more general class of split matrogenic graphs, we focus on this class of graphs for which we try to establish the membership to the PCG class.
    16 schema:editor Nbc6f187f524c4a0a85d97c34fcda08c8
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf N0ab123a1d42443d5ad1269b09114bae6
    21 schema:name On Relaxing the Constraints in Pairwise Compatibility Graphs
    22 schema:pagination 124-135
    23 schema:productId N25b5920f90ec4748915d7aaee87c90b1
    24 N66cc34ff78a3477a9af5c3f44ead0c25
    25 Nc131038093c647beb3c4ece335eb8c31
    26 schema:publisher N241ae35f7b58441da57f246c24b6ca82
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002922678
    28 https://doi.org/10.1007/978-3-642-28076-4_14
    29 schema:sdDatePublished 2019-04-15T17:11
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N343f631551574ef599d0eccdabb695ef
    32 schema:url http://link.springer.com/10.1007/978-3-642-28076-4_14
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset chapters
    35 rdf:type schema:Chapter
    36 N0ab123a1d42443d5ad1269b09114bae6 schema:isbn 978-3-642-28075-7
    37 978-3-642-28076-4
    38 schema:name WALCOM: Algorithms and Computation
    39 rdf:type schema:Book
    40 N241ae35f7b58441da57f246c24b6ca82 schema:location Berlin, Heidelberg
    41 schema:name Springer Berlin Heidelberg
    42 rdf:type schema:Organisation
    43 N25b5920f90ec4748915d7aaee87c90b1 schema:name readcube_id
    44 schema:value 0deb7f9e3eb5ae2a9f26d2c51019b958374b684160d9f6f618a5c4ef2f75fd44
    45 rdf:type schema:PropertyValue
    46 N343f631551574ef599d0eccdabb695ef schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 N4aeabbeccaf94575a0da702be65f80d0 rdf:first sg:person.011402427702.78
    49 rdf:rest N732a1778701641cb889c2c786cb35fad
    50 N66cc34ff78a3477a9af5c3f44ead0c25 schema:name dimensions_id
    51 schema:value pub.1002922678
    52 rdf:type schema:PropertyValue
    53 N732a1778701641cb889c2c786cb35fad rdf:first sg:person.01217440160.03
    54 rdf:rest rdf:nil
    55 N749b3c41a8f04d2b8deebb11d89ef0d3 schema:familyName Nakano
    56 schema:givenName Shin-ichi
    57 rdf:type schema:Person
    58 N7de510cac31a4899aa88f38b38eda721 rdf:first N749b3c41a8f04d2b8deebb11d89ef0d3
    59 rdf:rest rdf:nil
    60 N9d7d33c0c8a24842a1f80ccafba21b67 schema:familyName Rahman
    61 schema:givenName Md. Saidur
    62 rdf:type schema:Person
    63 Nbc6f187f524c4a0a85d97c34fcda08c8 rdf:first N9d7d33c0c8a24842a1f80ccafba21b67
    64 rdf:rest N7de510cac31a4899aa88f38b38eda721
    65 Nc131038093c647beb3c4ece335eb8c31 schema:name doi
    66 schema:value 10.1007/978-3-642-28076-4_14
    67 rdf:type schema:PropertyValue
    68 Necc8a07e3a2645c4993f585246eaf3ce rdf:first sg:person.013577775161.22
    69 rdf:rest N4aeabbeccaf94575a0da702be65f80d0
    70 anzsrc-for:11 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Medical and Health Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:1109 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Neurosciences
    75 rdf:type schema:DefinedTerm
    76 sg:person.011402427702.78 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    77 schema:familyName Petreschi
    78 schema:givenName Rossella
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011402427702.78
    80 rdf:type schema:Person
    81 sg:person.01217440160.03 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    82 schema:familyName Sinaimeri
    83 schema:givenName Blerina
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01217440160.03
    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-3-540-39763-2_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001248165
    92 https://doi.org/10.1007/978-3-540-39763-2_14
    93 rdf:type schema:CreativeWork
    94 sg:pub.10.1007/978-3-540-92182-0_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039610614
    95 https://doi.org/10.1007/978-3-540-92182-0_37
    96 rdf:type schema:CreativeWork
    97 sg:pub.10.1007/s12190-008-0204-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028947261
    98 https://doi.org/10.1007/s12190-008-0204-7
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1006/jagm.2001.1195 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023071535
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/j.disc.2009.10.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021270134
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/j.ipl.2006.01.004 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023650431
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1016/j.jda.2005.06.005 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052131278
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1142/s1793830910000917 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063025166
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1145/1435375.1435386 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034114283
    111 rdf:type schema:CreativeWork
    112 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    113 schema:name Department of Computer Science, “Sapienza” University of Rome, Italy, via Salaria 113, 00198 Roma
    114 rdf:type schema:Organization
     




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


    ...