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 N052223aa091045e784d8b933221c140c
    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 N455dc2157138495c8c82bc910d72291c
    16 N6c4fae9beff74969a5e7e0a5852d2af3
    17 sg:journal.1136398
    18 schema:name Pairwise compatibility graphs
    19 schema:pagination 479-503
    20 schema:productId N242955be2b6f45d1a59d566289a27ed8
    21 N298068b3b39e4a37acd57834c870d269
    22 N6219369c18264721877607314551e085
    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 N9cc99d6c3ba74508beb875fc7d0b1cca
    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 N052223aa091045e784d8b933221c140c rdf:first sg:person.014007317053.46
    33 rdf:rest Nad7b53d32e7c47ccb99b0209f933dfe5
    34 N242955be2b6f45d1a59d566289a27ed8 schema:name dimensions_id
    35 schema:value pub.1028947261
    36 rdf:type schema:PropertyValue
    37 N298068b3b39e4a37acd57834c870d269 schema:name doi
    38 schema:value 10.1007/s12190-008-0204-7
    39 rdf:type schema:PropertyValue
    40 N455dc2157138495c8c82bc910d72291c schema:issueNumber 1-2
    41 rdf:type schema:PublicationIssue
    42 N6219369c18264721877607314551e085 schema:name readcube_id
    43 schema:value 89e5d7f211fb8362c037d3130c5644dd88ff74c49be75bc351f360cd6311ac1f
    44 rdf:type schema:PropertyValue
    45 N6c4fae9beff74969a5e7e0a5852d2af3 schema:volumeNumber 30
    46 rdf:type schema:PublicationVolume
    47 N9cc99d6c3ba74508beb875fc7d0b1cca schema:name Springer Nature - SN SciGraph project
    48 rdf:type schema:Organization
    49 Nad7b53d32e7c47ccb99b0209f933dfe5 rdf:first sg:person.011655305237.68
    50 rdf:rest Nc30327f7bde845758f248ffa184c4049
    51 Nc30327f7bde845758f248ffa184c4049 rdf:first sg:person.01250200171.95
    52 rdf:rest rdf:nil
    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)


    ...