Pairwise compatibility graphs View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2009-05

AUTHORS

Muhammad Nur Yanhaona, K. S. M. Tozammel Hossain, M. Saidur Rahman

ABSTRACT

Given an edge weighted tree T and two non-negative real numbers dmin and dmax , a pairwise compatibility graph (PCG) of T is a graph G=(V,E), where each vertex u∈V corresponds to a leaf u of T and an edge (u,v)∈E if and only if dmin ≤distance(u,v)≤dmax in T. In this paper we give some properties of these graphs. We establish a relationship between pairwise compatibility graphs and chordal graphs. We show that all chordless cycles and single chord cycles are pairwise compatibility graphs. We also provide a linear-time algorithm for constructing trees that can generate graphs having cycles as their maximal biconnected subgraphs as PCGs. The techniques that we used to identify various types of pairwise compatibility graphs are quite generic and may be useful to discover other properties of these graphs. More... »

PAGES

479-503

References to SciGraph publications

  • 2002-01-29. Phylogenetic k-Root and Steiner k-Root in ALGORITHMS AND COMPUTATION
  • 2003. Efficient Generation of Uniform Samples from Phylogenetic Trees in ALGORITHMS IN BIOINFORMATICS
  • 1994-04. The maximum clique problem in JOURNAL OF GLOBAL OPTIMIZATION
  • 2008. Pairwise Compatibility Graphs in WALCOM: ALGORITHMS AND COMPUTATION
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s12190-008-0204-7

    DOI

    http://dx.doi.org/10.1007/s12190-008-0204-7

    DIMENSIONS

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


    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": "Bangladesh University of Engineering and Technology", 
              "id": "https://www.grid.ac/institutes/grid.411512.2", 
              "name": [
                "Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), 1000, Dhaka, Bangladesh"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Yanhaona", 
            "givenName": "Muhammad Nur", 
            "id": "sg:person.014007317053.46", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007317053.46"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Bangladesh University of Engineering and Technology", 
              "id": "https://www.grid.ac/institutes/grid.411512.2", 
              "name": [
                "Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), 1000, Dhaka, Bangladesh"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Hossain", 
            "givenName": "K. S. M. Tozammel", 
            "id": "sg:person.011655305237.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011655305237.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Bangladesh University of Engineering and Technology", 
              "id": "https://www.grid.ac/institutes/grid.411512.2", 
              "name": [
                "Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), 1000, Dhaka, Bangladesh"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Rahman", 
            "givenName": "M. Saidur", 
            "id": "sg:person.01250200171.95", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01250200171.95"
            ], 
            "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": "sg:pub.10.1007/978-3-540-77891-2_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014732771", 
              "https://doi.org/10.1007/978-3-540-77891-2_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-77891-2_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014732771", 
              "https://doi.org/10.1007/978-3-540-77891-2_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01098364", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028235387", 
              "https://doi.org/10.1007/bf01098364"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01098364", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028235387", 
              "https://doi.org/10.1007/bf01098364"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-40996-3_46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028915527", 
              "https://doi.org/10.1007/3-540-40996-3_46"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-40996-3_46", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028915527", 
              "https://doi.org/10.1007/3-540-40996-3_46"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1006/jagm.1998.9999", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032096870"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2009-05", 
        "datePublishedReg": "2009-05-01", 
        "description": "Given an edge weighted tree T and two non-negative real numbers dmin and dmax , a pairwise compatibility graph (PCG) of T is a graph G=(V,E), where each vertex u\u2208V corresponds to a leaf u of T and an edge (u,v)\u2208E if and only if dmin \u2264distance(u,v)\u2264dmax in T. In this paper we give some properties of these graphs. We establish a relationship between pairwise compatibility graphs and chordal graphs. We show that all chordless cycles and single chord cycles are pairwise compatibility graphs. We also provide a linear-time algorithm for constructing trees that can generate graphs having cycles as their maximal biconnected subgraphs as PCGs. The techniques that we used to identify various types of pairwise compatibility graphs are quite generic and may be useful to discover other properties of these graphs.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1007/s12190-008-0204-7", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136398", 
            "issn": [
              "1598-5865", 
              "1865-2085"
            ], 
            "name": "Journal of Applied Mathematics and Computing", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1-2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "30"
          }
        ], 
        "name": "Pairwise compatibility graphs", 
        "pagination": "479-503", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "89e5d7f211fb8362c037d3130c5644dd88ff74c49be75bc351f360cd6311ac1f"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s12190-008-0204-7"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1028947261"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s12190-008-0204-7", 
          "https://app.dimensions.ai/details/publication/pub.1028947261"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T19: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_00000522.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1007%2Fs12190-008-0204-7"
      }
    ]
     

    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/s12190-008-0204-7'

    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/s12190-008-0204-7'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s12190-008-0204-7'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s12190-008-0204-7'


     

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

    94 TRIPLES      21 PREDICATES      32 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s12190-008-0204-7 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N6cc4ba91ece34858b16f6c19a9e0bc20
    4 schema:citation sg:pub.10.1007/3-540-40996-3_46
    5 sg:pub.10.1007/978-3-540-39763-2_14
    6 sg:pub.10.1007/978-3-540-77891-2_21
    7 sg:pub.10.1007/bf01098364
    8 https://doi.org/10.1006/jagm.1998.9999
    9 schema:datePublished 2009-05
    10 schema:datePublishedReg 2009-05-01
    11 schema:description Given an edge weighted tree T and two non-negative real numbers dmin and dmax , a pairwise compatibility graph (PCG) of T is a graph G=(V,E), where each vertex u∈V corresponds to a leaf u of T and an edge (u,v)∈E if and only if dmin ≤distance(u,v)≤dmax in T. In this paper we give some properties of these graphs. We establish a relationship between pairwise compatibility graphs and chordal graphs. We show that all chordless cycles and single chord cycles are pairwise compatibility graphs. We also provide a linear-time algorithm for constructing trees that can generate graphs having cycles as their maximal biconnected subgraphs as PCGs. The techniques that we used to identify various types of pairwise compatibility graphs are quite generic and may be useful to discover other properties of these graphs.
    12 schema:genre research_article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N6d9c0514ece54b04ae755c93c66a0edd
    16 Ne22ef68ee40b48faa05d2d06ebe56736
    17 sg:journal.1136398
    18 schema:name Pairwise compatibility graphs
    19 schema:pagination 479-503
    20 schema:productId N0ec4338aa8d744e6a0e3eb13e9502cfd
    21 N6e65fdeb0ff540f9abb909a5e6e6d41f
    22 Nb4288d8789774709bcea28429c1ccc67
    23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028947261
    24 https://doi.org/10.1007/s12190-008-0204-7
    25 schema:sdDatePublished 2019-04-10T19:11
    26 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    27 schema:sdPublisher Nacf35cd6414a4a4dbaca244cc4bb96ce
    28 schema:url http://link.springer.com/10.1007%2Fs12190-008-0204-7
    29 sgo:license sg:explorer/license/
    30 sgo:sdDataset articles
    31 rdf:type schema:ScholarlyArticle
    32 N0ec4338aa8d744e6a0e3eb13e9502cfd schema:name doi
    33 schema:value 10.1007/s12190-008-0204-7
    34 rdf:type schema:PropertyValue
    35 N3aeae3e160e4464ca8e522aae84bf354 rdf:first sg:person.01250200171.95
    36 rdf:rest rdf:nil
    37 N6cc4ba91ece34858b16f6c19a9e0bc20 rdf:first sg:person.014007317053.46
    38 rdf:rest N8267d0ccf60f49888caee979df2b8ceb
    39 N6d9c0514ece54b04ae755c93c66a0edd schema:volumeNumber 30
    40 rdf:type schema:PublicationVolume
    41 N6e65fdeb0ff540f9abb909a5e6e6d41f schema:name dimensions_id
    42 schema:value pub.1028947261
    43 rdf:type schema:PropertyValue
    44 N8267d0ccf60f49888caee979df2b8ceb rdf:first sg:person.011655305237.68
    45 rdf:rest N3aeae3e160e4464ca8e522aae84bf354
    46 Nacf35cd6414a4a4dbaca244cc4bb96ce schema:name Springer Nature - SN SciGraph project
    47 rdf:type schema:Organization
    48 Nb4288d8789774709bcea28429c1ccc67 schema:name readcube_id
    49 schema:value 89e5d7f211fb8362c037d3130c5644dd88ff74c49be75bc351f360cd6311ac1f
    50 rdf:type schema:PropertyValue
    51 Ne22ef68ee40b48faa05d2d06ebe56736 schema:issueNumber 1-2
    52 rdf:type schema:PublicationIssue
    53 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    54 schema:name Information and Computing Sciences
    55 rdf:type schema:DefinedTerm
    56 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    57 schema:name Computation Theory and Mathematics
    58 rdf:type schema:DefinedTerm
    59 sg:journal.1136398 schema:issn 1598-5865
    60 1865-2085
    61 schema:name Journal of Applied Mathematics and Computing
    62 rdf:type schema:Periodical
    63 sg:person.011655305237.68 schema:affiliation https://www.grid.ac/institutes/grid.411512.2
    64 schema:familyName Hossain
    65 schema:givenName K. S. M. Tozammel
    66 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011655305237.68
    67 rdf:type schema:Person
    68 sg:person.01250200171.95 schema:affiliation https://www.grid.ac/institutes/grid.411512.2
    69 schema:familyName Rahman
    70 schema:givenName M. Saidur
    71 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01250200171.95
    72 rdf:type schema:Person
    73 sg:person.014007317053.46 schema:affiliation https://www.grid.ac/institutes/grid.411512.2
    74 schema:familyName Yanhaona
    75 schema:givenName Muhammad Nur
    76 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014007317053.46
    77 rdf:type schema:Person
    78 sg:pub.10.1007/3-540-40996-3_46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028915527
    79 https://doi.org/10.1007/3-540-40996-3_46
    80 rdf:type schema:CreativeWork
    81 sg:pub.10.1007/978-3-540-39763-2_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001248165
    82 https://doi.org/10.1007/978-3-540-39763-2_14
    83 rdf:type schema:CreativeWork
    84 sg:pub.10.1007/978-3-540-77891-2_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014732771
    85 https://doi.org/10.1007/978-3-540-77891-2_21
    86 rdf:type schema:CreativeWork
    87 sg:pub.10.1007/bf01098364 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028235387
    88 https://doi.org/10.1007/bf01098364
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1006/jagm.1998.9999 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032096870
    91 rdf:type schema:CreativeWork
    92 https://www.grid.ac/institutes/grid.411512.2 schema:alternateName Bangladesh University of Engineering and Technology
    93 schema:name Department of Computer Science and Engineering, Bangladesh University of Engineering and Technology (BUET), 1000, Dhaka, Bangladesh
    94 rdf:type schema:Organization
     




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


    ...