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 N060ed8a94c4143a2b60371f0b290f245
    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 Ncd501cfad83a49c08f0718a81c10e512
    17 schema:genre chapter
    18 schema:inLanguage en
    19 schema:isAccessibleForFree true
    20 schema:isPartOf Nbca384ec0277428b887b1138238fc4dd
    21 schema:name On Relaxing the Constraints in Pairwise Compatibility Graphs
    22 schema:pagination 124-135
    23 schema:productId N0979eedd5d6b4774827b905461a77629
    24 N3aa8d01f0b3c4baa9ce31414db845501
    25 Nd60a2ee0a8884df7bb8b12f07d453058
    26 schema:publisher Nbf85770d845f4b199f5eeb0ff5c8ac54
    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 Ndf6f451babc742ebb1a89ddb4b9939ae
    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 N060ed8a94c4143a2b60371f0b290f245 rdf:first sg:person.013577775161.22
    37 rdf:rest N869ff933924943eda75cd458d3da1020
    38 N0979eedd5d6b4774827b905461a77629 schema:name readcube_id
    39 schema:value 0deb7f9e3eb5ae2a9f26d2c51019b958374b684160d9f6f618a5c4ef2f75fd44
    40 rdf:type schema:PropertyValue
    41 N3aa8d01f0b3c4baa9ce31414db845501 schema:name doi
    42 schema:value 10.1007/978-3-642-28076-4_14
    43 rdf:type schema:PropertyValue
    44 N5e75dbfc960a47d2a7b292d77ac0c388 rdf:first Nd6efbc103f884550944478ed247eaf39
    45 rdf:rest rdf:nil
    46 N7904aff378f647c3afaa8c1d30a0cac0 schema:familyName Rahman
    47 schema:givenName Md. Saidur
    48 rdf:type schema:Person
    49 N8514426d95cf463ca4fdb280540f4804 rdf:first sg:person.01217440160.03
    50 rdf:rest rdf:nil
    51 N869ff933924943eda75cd458d3da1020 rdf:first sg:person.011402427702.78
    52 rdf:rest N8514426d95cf463ca4fdb280540f4804
    53 Nbca384ec0277428b887b1138238fc4dd schema:isbn 978-3-642-28075-7
    54 978-3-642-28076-4
    55 schema:name WALCOM: Algorithms and Computation
    56 rdf:type schema:Book
    57 Nbf85770d845f4b199f5eeb0ff5c8ac54 schema:location Berlin, Heidelberg
    58 schema:name Springer Berlin Heidelberg
    59 rdf:type schema:Organisation
    60 Ncd501cfad83a49c08f0718a81c10e512 rdf:first N7904aff378f647c3afaa8c1d30a0cac0
    61 rdf:rest N5e75dbfc960a47d2a7b292d77ac0c388
    62 Nd60a2ee0a8884df7bb8b12f07d453058 schema:name dimensions_id
    63 schema:value pub.1002922678
    64 rdf:type schema:PropertyValue
    65 Nd6efbc103f884550944478ed247eaf39 schema:familyName Nakano
    66 schema:givenName Shin-ichi
    67 rdf:type schema:Person
    68 Ndf6f451babc742ebb1a89ddb4b9939ae schema:name Springer Nature - SN SciGraph project
    69 rdf:type schema:Organization
    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)


    ...