The Full Steiner Tree Problem in Phylogeny View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2002

AUTHORS

Chin Lung Lu , Chuan Yi Tang , Richard Chia-Tung Lee

ABSTRACT

Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R ⊂ V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 5/3-approximation algorithm to find an approximate solution for the problem. More... »

PAGES

107-116

References to SciGraph publications

  • 1972. Reducibility among Combinatorial Problems in COMPLEXITY OF COMPUTER COMPUTATIONS
  • 2001. Approximation Algorithms for the Steiner Tree Problem in Graphs in STEINER TREES IN INDUSTRY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/3-540-45655-4_13

    DOI

    http://dx.doi.org/10.1007/3-540-45655-4_13

    DIMENSIONS

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


    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": "National Center for High-Performance Computing", 
              "id": "https://www.grid.ac/institutes/grid.462649.b", 
              "name": [
                "National Center for High-Performance Computing, P.O. Box 19-136, Hsinchu, Taiwan 300, R.O.C."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lu", 
            "givenName": "Chin Lung", 
            "id": "sg:person.016502771037.22", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Tsing Hua University", 
              "id": "https://www.grid.ac/institutes/grid.38348.34", 
              "name": [
                "Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300, R.O.C."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tang", 
            "givenName": "Chuan Yi", 
            "id": "sg:person.01312526135.27", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "National Chi Nan University", 
              "id": "https://www.grid.ac/institutes/grid.412044.7", 
              "name": [
                "Department of Computer Science and Information Engineering, National Chi-Nan University, Puli, Nantou Hsien, Taiwan 545, R.O.C."
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lee", 
            "givenName": "Richard Chia-Tung", 
            "id": "sg:person.014253510462.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014253510462.28"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-1-4684-2001-2_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007977430", 
              "https://doi.org/10.1007/978-1-4684-2001-2_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(89)90039-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014893893"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-0255-1_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021792328", 
              "https://doi.org/10.1007/978-1-4613-0255-1_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-4613-0255-1_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021792328", 
              "https://doi.org/10.1007/978-1-4613-0255-1_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/278298.278306", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022637686"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/0020739830140103", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026261721"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/s0196-8858(82)80004-3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1032724280"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0022-0000(91)90023-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043200457"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0167-6377(86)90008-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047117003"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0132071", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062839609"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0132072", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062839610"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002", 
        "datePublishedReg": "2002-01-01", 
        "description": "Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R \u2282 V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 5/3-approximation algorithm to find an approximate solution for the problem.", 
        "editor": [
          {
            "familyName": "Ibarra", 
            "givenName": "Oscar H.", 
            "type": "Person"
          }, 
          {
            "familyName": "Zhang", 
            "givenName": "Louxin", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/3-540-45655-4_13", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-540-43996-7", 
            "978-3-540-45655-1"
          ], 
          "name": "Computing and Combinatorics", 
          "type": "Book"
        }, 
        "name": "The Full Steiner Tree Problem in Phylogeny", 
        "pagination": "107-116", 
        "productId": [
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/3-540-45655-4_13"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "aa66be3b39027c08d711ff4eaefd0471f24525c51056e035765a7355cd2337b5"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1035771232"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/3-540-45655-4_13", 
          "https://app.dimensions.ai/details/publication/pub.1035771232"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-15T20:07", 
        "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_8687_00000265.jsonl", 
        "type": "Chapter", 
        "url": "http://link.springer.com/10.1007/3-540-45655-4_13"
      }
    ]
     

    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-45655-4_13'

    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-45655-4_13'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-45655-4_13'

    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-45655-4_13'


     

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

    122 TRIPLES      23 PREDICATES      37 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/3-540-45655-4_13 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 schema:author N61a54b5e40b7466bbea06f4bbf6c5d81
    4 schema:citation sg:pub.10.1007/978-1-4613-0255-1_7
    5 sg:pub.10.1007/978-1-4684-2001-2_9
    6 https://doi.org/10.1016/0020-0190(89)90039-2
    7 https://doi.org/10.1016/0022-0000(91)90023-x
    8 https://doi.org/10.1016/0167-6377(86)90008-8
    9 https://doi.org/10.1016/s0196-8858(82)80004-3
    10 https://doi.org/10.1080/0020739830140103
    11 https://doi.org/10.1137/0132071
    12 https://doi.org/10.1137/0132072
    13 https://doi.org/10.1145/278298.278306
    14 schema:datePublished 2002
    15 schema:datePublishedReg 2002-01-01
    16 schema:description Motivated by the reconstruction of phylogenetic tree in biology, we study the full Steiner tree problem in this paper. Given a complete graph G = (V, E) with a length function on E and a proper subset R ⊂ V, the problem is to find a full Steiner tree of minimum length in G, which is a kind of Steiner tree with all the vertices of R as its leaves. In this paper, we show that this problem is NP-complete and MAX SNP-hard, even when the lengths of the edges are restricted to either 1 or 2. For the instances with lengths either 1 or 2, we give a 5/3-approximation algorithm to find an approximate solution for the problem.
    17 schema:editor N90b27375d28a4443970f6d5815be1dfe
    18 schema:genre chapter
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf Ne9ce0f1eae4940fa80075277fffeb8a4
    22 schema:name The Full Steiner Tree Problem in Phylogeny
    23 schema:pagination 107-116
    24 schema:productId N0eeb24be1c18491e8ef71aad2316696e
    25 N4abd950d7491411587b87000d9555a8c
    26 N6cd944e4b54446bbacb69c61d56c9a1f
    27 schema:publisher Nd665d5baf944479096265e0e5d1bfd8f
    28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035771232
    29 https://doi.org/10.1007/3-540-45655-4_13
    30 schema:sdDatePublished 2019-04-15T20:07
    31 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    32 schema:sdPublisher N13b43770c5ad4215ad6df52173a05d49
    33 schema:url http://link.springer.com/10.1007/3-540-45655-4_13
    34 sgo:license sg:explorer/license/
    35 sgo:sdDataset chapters
    36 rdf:type schema:Chapter
    37 N0eeb24be1c18491e8ef71aad2316696e schema:name dimensions_id
    38 schema:value pub.1035771232
    39 rdf:type schema:PropertyValue
    40 N13b43770c5ad4215ad6df52173a05d49 schema:name Springer Nature - SN SciGraph project
    41 rdf:type schema:Organization
    42 N1b306ccc6741435dba5a3d713dfc64f0 rdf:first N5430591be982419f8f61512c0e9280a9
    43 rdf:rest rdf:nil
    44 N3b2d70e66ba844acb3c1756e7ac1ecbc rdf:first sg:person.01312526135.27
    45 rdf:rest Nf7c930f86f5f4f6ab8c03106cd954446
    46 N4abd950d7491411587b87000d9555a8c schema:name readcube_id
    47 schema:value aa66be3b39027c08d711ff4eaefd0471f24525c51056e035765a7355cd2337b5
    48 rdf:type schema:PropertyValue
    49 N5430591be982419f8f61512c0e9280a9 schema:familyName Zhang
    50 schema:givenName Louxin
    51 rdf:type schema:Person
    52 N61a54b5e40b7466bbea06f4bbf6c5d81 rdf:first sg:person.016502771037.22
    53 rdf:rest N3b2d70e66ba844acb3c1756e7ac1ecbc
    54 N6cd944e4b54446bbacb69c61d56c9a1f schema:name doi
    55 schema:value 10.1007/3-540-45655-4_13
    56 rdf:type schema:PropertyValue
    57 N90b27375d28a4443970f6d5815be1dfe rdf:first Nc8a73dfc129f4f0c8e3de8912dc4f790
    58 rdf:rest N1b306ccc6741435dba5a3d713dfc64f0
    59 Nc8a73dfc129f4f0c8e3de8912dc4f790 schema:familyName Ibarra
    60 schema:givenName Oscar H.
    61 rdf:type schema:Person
    62 Nd665d5baf944479096265e0e5d1bfd8f schema:location Berlin, Heidelberg
    63 schema:name Springer Berlin Heidelberg
    64 rdf:type schema:Organisation
    65 Ne9ce0f1eae4940fa80075277fffeb8a4 schema:isbn 978-3-540-43996-7
    66 978-3-540-45655-1
    67 schema:name Computing and Combinatorics
    68 rdf:type schema:Book
    69 Nf7c930f86f5f4f6ab8c03106cd954446 rdf:first sg:person.014253510462.28
    70 rdf:rest rdf:nil
    71 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    72 schema:name Information and Computing Sciences
    73 rdf:type schema:DefinedTerm
    74 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    75 schema:name Computation Theory and Mathematics
    76 rdf:type schema:DefinedTerm
    77 sg:person.01312526135.27 schema:affiliation https://www.grid.ac/institutes/grid.38348.34
    78 schema:familyName Tang
    79 schema:givenName Chuan Yi
    80 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01312526135.27
    81 rdf:type schema:Person
    82 sg:person.014253510462.28 schema:affiliation https://www.grid.ac/institutes/grid.412044.7
    83 schema:familyName Lee
    84 schema:givenName Richard Chia-Tung
    85 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014253510462.28
    86 rdf:type schema:Person
    87 sg:person.016502771037.22 schema:affiliation https://www.grid.ac/institutes/grid.462649.b
    88 schema:familyName Lu
    89 schema:givenName Chin Lung
    90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016502771037.22
    91 rdf:type schema:Person
    92 sg:pub.10.1007/978-1-4613-0255-1_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021792328
    93 https://doi.org/10.1007/978-1-4613-0255-1_7
    94 rdf:type schema:CreativeWork
    95 sg:pub.10.1007/978-1-4684-2001-2_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007977430
    96 https://doi.org/10.1007/978-1-4684-2001-2_9
    97 rdf:type schema:CreativeWork
    98 https://doi.org/10.1016/0020-0190(89)90039-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014893893
    99 rdf:type schema:CreativeWork
    100 https://doi.org/10.1016/0022-0000(91)90023-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1043200457
    101 rdf:type schema:CreativeWork
    102 https://doi.org/10.1016/0167-6377(86)90008-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047117003
    103 rdf:type schema:CreativeWork
    104 https://doi.org/10.1016/s0196-8858(82)80004-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032724280
    105 rdf:type schema:CreativeWork
    106 https://doi.org/10.1080/0020739830140103 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026261721
    107 rdf:type schema:CreativeWork
    108 https://doi.org/10.1137/0132071 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839609
    109 rdf:type schema:CreativeWork
    110 https://doi.org/10.1137/0132072 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062839610
    111 rdf:type schema:CreativeWork
    112 https://doi.org/10.1145/278298.278306 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022637686
    113 rdf:type schema:CreativeWork
    114 https://www.grid.ac/institutes/grid.38348.34 schema:alternateName National Tsing Hua University
    115 schema:name Department of Computer Science, National Tsing Hua University, Hsinchu, Taiwan 300, R.O.C.
    116 rdf:type schema:Organization
    117 https://www.grid.ac/institutes/grid.412044.7 schema:alternateName National Chi Nan University
    118 schema:name Department of Computer Science and Information Engineering, National Chi-Nan University, Puli, Nantou Hsien, Taiwan 545, R.O.C.
    119 rdf:type schema:Organization
    120 https://www.grid.ac/institutes/grid.462649.b schema:alternateName National Center for High-Performance Computing
    121 schema:name National Center for High-Performance Computing, P.O. Box 19-136, Hsinchu, Taiwan 300, R.O.C.
    122 rdf:type schema:Organization
     




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


    ...