An Improved Approximation Algorithm for rSPR Distance View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-07-20

AUTHORS

Zhi-Zhong Chen , Eita Machida , Lusheng Wang

ABSTRACT

The problem of computing the rSPR distance of two given trees has many applications but is unfortunately NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2.5 and it was open whether a better approximation algorithm for rSPR distance exists. In this paper, we answer this question in the affirmative by presenting an approximation algorithm for rSPR distance that achieves a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{7}{3}$$\end{document}. Our algorithm is based on the new notion of key and several new structural lemmas. More... »

PAGES

468-479

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-42634-1_38

DOI

http://dx.doi.org/10.1007/978-3-319-42634-1_38

DIMENSIONS

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


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 Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chen", 
        "givenName": "Zhi-Zhong", 
        "id": "sg:person.015654265661.98", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan", 
          "id": "http://www.grid.ac/institutes/grid.412773.4", 
          "name": [
            "Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Machida", 
        "givenName": "Eita", 
        "id": "sg:person.014542220455.48", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014542220455.48"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Lusheng", 
        "id": "sg:person.01105113721.52", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2016-07-20", 
    "datePublishedReg": "2016-07-20", 
    "description": "The problem of computing the rSPR distance of two given trees has many applications but is unfortunately NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2.5 and it was open whether a better approximation algorithm for rSPR distance exists. In this paper, we answer this question in the affirmative by presenting an approximation algorithm for rSPR distance that achieves a ratio of \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\frac{7}{3}$$\\end{document}. Our algorithm is based on the new notion of key and several new structural lemmas.", 
    "editor": [
      {
        "familyName": "Dinh", 
        "givenName": "Thang N.", 
        "type": "Person"
      }, 
      {
        "familyName": "Thai", 
        "givenName": "My T.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-42634-1_38", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-319-42633-4", 
        "978-3-319-42634-1"
      ], 
      "name": "Computing and Combinatorics", 
      "type": "Book"
    }, 
    "keywords": [
      "distance", 
      "applications", 
      "ratio", 
      "rSPR distance", 
      "NPs", 
      "best approximation algorithm", 
      "approximation algorithm", 
      "problem", 
      "algorithm", 
      "paper", 
      "questions", 
      "new notion", 
      "structural lemma", 
      "improved approximation algorithms", 
      "trees", 
      "notion", 
      "lemma"
    ], 
    "name": "An Improved Approximation Algorithm for rSPR Distance", 
    "pagination": "468-479", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1011246733"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-42634-1_38"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-42634-1_38", 
      "https://app.dimensions.ai/details/publication/pub.1011246733"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:46", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_361.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-42634-1_38"
  }
]
 

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-319-42634-1_38'

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-319-42634-1_38'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-42634-1_38'

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-319-42634-1_38'


 

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

99 TRIPLES      23 PREDICATES      42 URIs      35 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-42634-1_38 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author N45c913ec108343c798607421afe9b1f7
4 schema:datePublished 2016-07-20
5 schema:datePublishedReg 2016-07-20
6 schema:description The problem of computing the rSPR distance of two given trees has many applications but is unfortunately NP-hard. The previously best approximation algorithm for rSPR distance achieves a ratio of 2.5 and it was open whether a better approximation algorithm for rSPR distance exists. In this paper, we answer this question in the affirmative by presenting an approximation algorithm for rSPR distance that achieves a ratio of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\frac{7}{3}$$\end{document}. Our algorithm is based on the new notion of key and several new structural lemmas.
7 schema:editor N3474a9f1f8004dbe9ccf786a5604b015
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nd096f13f89394e61bdae275c68d17f9e
12 schema:keywords NPs
13 algorithm
14 applications
15 approximation algorithm
16 best approximation algorithm
17 distance
18 improved approximation algorithms
19 lemma
20 new notion
21 notion
22 paper
23 problem
24 questions
25 rSPR distance
26 ratio
27 structural lemma
28 trees
29 schema:name An Improved Approximation Algorithm for rSPR Distance
30 schema:pagination 468-479
31 schema:productId N458d9065f8f8403882c8abf85c79a12e
32 N6a86e6ab277d40eba9219420e470f623
33 schema:publisher N9a59af843e704ee6acb6b78e9dfb29c5
34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011246733
35 https://doi.org/10.1007/978-3-319-42634-1_38
36 schema:sdDatePublished 2022-05-20T07:46
37 schema:sdLicense https://scigraph.springernature.com/explorer/license/
38 schema:sdPublisher Nab5b54d52dc3420eb302e4fa1131c362
39 schema:url https://doi.org/10.1007/978-3-319-42634-1_38
40 sgo:license sg:explorer/license/
41 sgo:sdDataset chapters
42 rdf:type schema:Chapter
43 N3474a9f1f8004dbe9ccf786a5604b015 rdf:first Nd061be3e7aa040dcb74bdebcd1281d8e
44 rdf:rest N92beb5f1ba0d4b48992b9280ab6fbbf8
45 N458d9065f8f8403882c8abf85c79a12e schema:name doi
46 schema:value 10.1007/978-3-319-42634-1_38
47 rdf:type schema:PropertyValue
48 N45c913ec108343c798607421afe9b1f7 rdf:first sg:person.015654265661.98
49 rdf:rest Nadab4209750c4cc2a7b3d54c9c3a756f
50 N4c6633f238f84819bd5ed844d5129cee schema:familyName Thai
51 schema:givenName My T.
52 rdf:type schema:Person
53 N6a86e6ab277d40eba9219420e470f623 schema:name dimensions_id
54 schema:value pub.1011246733
55 rdf:type schema:PropertyValue
56 N81ef5494fb32438493dadbb645a48762 rdf:first sg:person.01105113721.52
57 rdf:rest rdf:nil
58 N92beb5f1ba0d4b48992b9280ab6fbbf8 rdf:first N4c6633f238f84819bd5ed844d5129cee
59 rdf:rest rdf:nil
60 N9a59af843e704ee6acb6b78e9dfb29c5 schema:name Springer Nature
61 rdf:type schema:Organisation
62 Nab5b54d52dc3420eb302e4fa1131c362 schema:name Springer Nature - SN SciGraph project
63 rdf:type schema:Organization
64 Nadab4209750c4cc2a7b3d54c9c3a756f rdf:first sg:person.014542220455.48
65 rdf:rest N81ef5494fb32438493dadbb645a48762
66 Nd061be3e7aa040dcb74bdebcd1281d8e schema:familyName Dinh
67 schema:givenName Thang N.
68 rdf:type schema:Person
69 Nd096f13f89394e61bdae275c68d17f9e schema:isbn 978-3-319-42633-4
70 978-3-319-42634-1
71 schema:name Computing and Combinatorics
72 rdf:type schema:Book
73 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
74 schema:name Information and Computing Sciences
75 rdf:type schema:DefinedTerm
76 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
77 schema:name Computation Theory and Mathematics
78 rdf:type schema:DefinedTerm
79 sg:person.01105113721.52 schema:affiliation grid-institutes:None
80 schema:familyName Wang
81 schema:givenName Lusheng
82 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01105113721.52
83 rdf:type schema:Person
84 sg:person.014542220455.48 schema:affiliation grid-institutes:grid.412773.4
85 schema:familyName Machida
86 schema:givenName Eita
87 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014542220455.48
88 rdf:type schema:Person
89 sg:person.015654265661.98 schema:affiliation grid-institutes:grid.412773.4
90 schema:familyName Chen
91 schema:givenName Zhi-Zhong
92 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015654265661.98
93 rdf:type schema:Person
94 grid-institutes:None schema:alternateName Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
95 schema:name Department of Computer Science, City University of Hong Kong, Tat Chee Avenue, Kowloon, Hong Kong SAR
96 rdf:type schema:Organization
97 grid-institutes:grid.412773.4 schema:alternateName Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
98 schema:name Department of Information System Design, Tokyo Denki University, 350-0394, Hatoyama, Saitama, Japan
99 rdf:type schema:Organization
 




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


...