An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2004

AUTHORS

Hsin-Fu Chen , Maw-Shang Chang

ABSTRACT

The minimum ultrametric tree problem is an NP-hard evolutionary tree construction problem. Wu et al. proposed a branch-and-bound algorithm that solves the minimum ultrametric tree problem to optimality in [11]. In this paper, we use a look-ahead approach to computing a tighter lower bound for a subproblem. Besides we propose to use the persistent data structure to speedup the branch-and-bound algorithm. Experimental results show that our algorithm outperforms the previous one. We believe that the approach used in the paper can be adapted to speedup other branch-and-bound algorithms. More... »

PAGES

282-293

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-30551-4_26

DOI

http://dx.doi.org/10.1007/978-3-540-30551-4_26

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, 621, Chiayi, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, 621, Chiayi, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Hsin-Fu", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, 621, Chiayi, Taiwan", 
          "id": "http://www.grid.ac/institutes/grid.412047.4", 
          "name": [
            "Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, 621, Chiayi, Taiwan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chang", 
        "givenName": "Maw-Shang", 
        "id": "sg:person.013174232477.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2004", 
    "datePublishedReg": "2004-01-01", 
    "description": "The minimum ultrametric tree problem is an NP-hard evolutionary tree construction problem. Wu et al. proposed a branch-and-bound algorithm that solves the minimum ultrametric tree problem to optimality in [11]. In this paper, we use a look-ahead approach to computing a tighter lower bound for a subproblem. Besides we propose to use the persistent data structure to speedup the branch-and-bound algorithm. Experimental results show that our algorithm outperforms the previous one. We believe that the approach used in the paper can be adapted to speedup other branch-and-bound algorithms.", 
    "editor": [
      {
        "familyName": "Fleischer", 
        "givenName": "Rudolf", 
        "type": "Person"
      }, 
      {
        "familyName": "Trippen", 
        "givenName": "Gerhard", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-540-30551-4_26", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-24131-7", 
        "978-3-540-30551-4"
      ], 
      "name": "Algorithms and Computation", 
      "type": "Book"
    }, 
    "keywords": [
      "tree problem", 
      "persistent data structures", 
      "look-ahead approach", 
      "tree construction problem", 
      "efficient exact algorithm", 
      "data structure", 
      "exact algorithm", 
      "algorithm", 
      "construction problem", 
      "experimental results", 
      "subproblems", 
      "optimality", 
      "branches", 
      "results", 
      "structure", 
      "problem", 
      "paper", 
      "approach", 
      "minimum ultrametric tree problem", 
      "ultrametric tree problem", 
      "NP-hard evolutionary tree construction problem", 
      "evolutionary tree construction problem"
    ], 
    "name": "An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem", 
    "pagination": "282-293", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1045432111"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-540-30551-4_26"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-540-30551-4_26", 
      "https://app.dimensions.ai/details/publication/pub.1045432111"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-11-01T18:57", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211101/entities/gbq_results/chapter/chapter_356.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-540-30551-4_26"
  }
]
 

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-540-30551-4_26'

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-540-30551-4_26'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-30551-4_26'

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-540-30551-4_26'


 

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

93 TRIPLES      23 PREDICATES      48 URIs      41 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-540-30551-4_26 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N087b14f9eb3f4047a4478c3e6fd1426a
4 schema:datePublished 2004
5 schema:datePublishedReg 2004-01-01
6 schema:description The minimum ultrametric tree problem is an NP-hard evolutionary tree construction problem. Wu et al. proposed a branch-and-bound algorithm that solves the minimum ultrametric tree problem to optimality in [11]. In this paper, we use a look-ahead approach to computing a tighter lower bound for a subproblem. Besides we propose to use the persistent data structure to speedup the branch-and-bound algorithm. Experimental results show that our algorithm outperforms the previous one. We believe that the approach used in the paper can be adapted to speedup other branch-and-bound algorithms.
7 schema:editor Na3aadf4925fb41208715d62aa30c4711
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N71ccffe229a3481a89aef4a1d748c269
12 schema:keywords NP-hard evolutionary tree construction problem
13 algorithm
14 approach
15 branches
16 construction problem
17 data structure
18 efficient exact algorithm
19 evolutionary tree construction problem
20 exact algorithm
21 experimental results
22 look-ahead approach
23 minimum ultrametric tree problem
24 optimality
25 paper
26 persistent data structures
27 problem
28 results
29 structure
30 subproblems
31 tree construction problem
32 tree problem
33 ultrametric tree problem
34 schema:name An Efficient Exact Algorithm for the Minimum Ultrametric Tree Problem
35 schema:pagination 282-293
36 schema:productId Nc2a051f510d14780b3ad0e88e83bfd06
37 Ne48c708666da48e4b8c5917b1e38460a
38 schema:publisher Nd30af18ec0484af98142d2772752f83f
39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045432111
40 https://doi.org/10.1007/978-3-540-30551-4_26
41 schema:sdDatePublished 2021-11-01T18:57
42 schema:sdLicense https://scigraph.springernature.com/explorer/license/
43 schema:sdPublisher N161cf13bb3d44b99ac7595d9f91ab559
44 schema:url https://doi.org/10.1007/978-3-540-30551-4_26
45 sgo:license sg:explorer/license/
46 sgo:sdDataset chapters
47 rdf:type schema:Chapter
48 N087b14f9eb3f4047a4478c3e6fd1426a rdf:first Nc885e7a04f5c49aea80a33bb8a6eaf03
49 rdf:rest Nc176bf578f6848af9194177ed9ac4bc0
50 N161cf13bb3d44b99ac7595d9f91ab559 schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N71ccffe229a3481a89aef4a1d748c269 schema:isbn 978-3-540-24131-7
53 978-3-540-30551-4
54 schema:name Algorithms and Computation
55 rdf:type schema:Book
56 N8bc6ec8a039b4605a4f2ee4e992e9029 rdf:first N9b43df51e34a48b5a8dd32576c4f3388
57 rdf:rest rdf:nil
58 N9b43df51e34a48b5a8dd32576c4f3388 schema:familyName Trippen
59 schema:givenName Gerhard
60 rdf:type schema:Person
61 Na3aadf4925fb41208715d62aa30c4711 rdf:first Ndcf31c2af4144c93a5e932f47c26d045
62 rdf:rest N8bc6ec8a039b4605a4f2ee4e992e9029
63 Nc176bf578f6848af9194177ed9ac4bc0 rdf:first sg:person.013174232477.45
64 rdf:rest rdf:nil
65 Nc2a051f510d14780b3ad0e88e83bfd06 schema:name dimensions_id
66 schema:value pub.1045432111
67 rdf:type schema:PropertyValue
68 Nc885e7a04f5c49aea80a33bb8a6eaf03 schema:affiliation grid-institutes:grid.412047.4
69 schema:familyName Chen
70 schema:givenName Hsin-Fu
71 rdf:type schema:Person
72 Nd30af18ec0484af98142d2772752f83f schema:name Springer Nature
73 rdf:type schema:Organisation
74 Ndcf31c2af4144c93a5e932f47c26d045 schema:familyName Fleischer
75 schema:givenName Rudolf
76 rdf:type schema:Person
77 Ne48c708666da48e4b8c5917b1e38460a schema:name doi
78 schema:value 10.1007/978-3-540-30551-4_26
79 rdf:type schema:PropertyValue
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.013174232477.45 schema:affiliation grid-institutes:grid.412047.4
87 schema:familyName Chang
88 schema:givenName Maw-Shang
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013174232477.45
90 rdf:type schema:Person
91 grid-institutes:grid.412047.4 schema:alternateName Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, 621, Chiayi, Taiwan
92 schema:name Department of Computer Science and Information Engineering, National Chung Cheng University, Ming-Shiun, 621, Chiayi, Taiwan
93 rdf:type schema:Organization
 




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


...