An improved approximation algorithm for rSPR distance

Zhi-Zhong Chen; Eita Machida; Lusheng Wang

doi:10.1007/978-3-319-42634-1_38

An improved approximation algorithm for rSPR distance

Zhi-Zhong Chen^*, Eita Machida, Lusheng Wang

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

6 Citations (Scopus)

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 7/3. Our algorithm is based on the new notion of key and several new structural lemmas.

Original language	English
Title of host publication	Computing and Combinatorics
Subtitle of host publication	22nd International Conference, COCOON 2016, Proceedings
Editors	Thang N. Dinh, My T. Thai
Publisher	Springer Verlag
Pages	468-479
Volume	9797
ISBN (Print)	9783319426334
DOIs	https://doi.org/10.1007/978-3-319-42634-1_38
Publication status	Published - 2016
Event	22nd International Conference on Computing and Combinatorics, COCOON 2016 - Ho Chi Minh City, Viet Nam Duration: 2 Aug 2016 → 4 Aug 2016

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9797
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	22nd International Conference on Computing and Combinatorics, COCOON 2016
Place	Viet Nam
City	Ho Chi Minh City
Period	2/08/16 → 4/08/16

Access Output

10.1007/978-3-319-42634-1_38

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Chen, Z.-Z., Machida, E., & Wang, L. (2016). An improved approximation algorithm for rSPR distance. In T. N. Dinh, & M. T. Thai (Eds.), Computing and Combinatorics: 22nd International Conference, COCOON 2016, Proceedings (Vol. 9797, pp. 468-479). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9797). Springer Verlag. https://doi.org/10.1007/978-3-319-42634-1_38

Chen, Zhi-Zhong ; Machida, Eita ; Wang, Lusheng. / An improved approximation algorithm for rSPR distance. Computing and Combinatorics: 22nd International Conference, COCOON 2016, Proceedings. editor / Thang N. Dinh ; My T. Thai. Vol. 9797 Springer Verlag, 2016. pp. 468-479 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c19674c3da90480693ee5c67a7b18159,

title = "An improved approximation algorithm for rSPR distance",

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 7/3. Our algorithm is based on the new notion of key and several new structural lemmas.",

author = "Zhi-Zhong Chen and Eita Machida and Lusheng Wang",

year = "2016",

doi = "10.1007/978-3-319-42634-1_38",

language = "English",

isbn = "9783319426334",

volume = "9797",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "468--479",

editor = "Dinh, {Thang N.} and Thai, {My T.}",

booktitle = "Computing and Combinatorics",

address = "Germany",

note = "22nd International Conference on Computing and Combinatorics, COCOON 2016 ; Conference date: 02-08-2016 Through 04-08-2016",

}

Chen, Z-Z, Machida, E & Wang, L 2016, An improved approximation algorithm for rSPR distance. in TN Dinh & MT Thai (eds), Computing and Combinatorics: 22nd International Conference, COCOON 2016, Proceedings. vol. 9797, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9797, Springer Verlag, pp. 468-479, 22nd International Conference on Computing and Combinatorics, COCOON 2016, Ho Chi Minh City, Viet Nam, 2/08/16. https://doi.org/10.1007/978-3-319-42634-1_38

An improved approximation algorithm for rSPR distance. / Chen, Zhi-Zhong; Machida, Eita; Wang, Lusheng.
Computing and Combinatorics: 22nd International Conference, COCOON 2016, Proceedings. ed. / Thang N. Dinh; My T. Thai. Vol. 9797 Springer Verlag, 2016. p. 468-479 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9797).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - An improved approximation algorithm for rSPR distance

AU - Chen, Zhi-Zhong

AU - Machida, Eita

AU - Wang, Lusheng

PY - 2016

Y1 - 2016

N2 - 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 7/3. Our algorithm is based on the new notion of key and several new structural lemmas.

AB - 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 7/3. Our algorithm is based on the new notion of key and several new structural lemmas.

UR - http://www.scopus.com/inward/record.url?scp=84979265849&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-84979265849&origin=recordpage

U2 - 10.1007/978-3-319-42634-1_38

DO - 10.1007/978-3-319-42634-1_38

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9783319426334

VL - 9797

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 468

EP - 479

BT - Computing and Combinatorics

A2 - Dinh, Thang N.

A2 - Thai, My T.

PB - Springer Verlag

T2 - 22nd International Conference on Computing and Combinatorics, COCOON 2016

Y2 - 2 August 2016 through 4 August 2016

ER -

Chen ZZ, Machida E, Wang L. An improved approximation algorithm for rSPR distance. In Dinh TN, Thai MT, editors, Computing and Combinatorics: 22nd International Conference, COCOON 2016, Proceedings. Vol. 9797. Springer Verlag. 2016. p. 468-479. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-42634-1_38

An improved approximation algorithm for rSPR distance

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this