On the complexity of inferring rooted evolutionary trees

Jesper Andreas Jansson

On the complexity of inferring rooted evolutionary trees

Jesper Andreas Jansson

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

28 Citations (Scopus)

Abstract

We prove that the maximum inferred local consensus tree problem is NP-complete, thus resolving an open question from [3].

Original language	English
Title of host publication	Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001)
Editors	Jayme Luiz Szwarcfiter
Pages	50-53
Number of pages	4
Volume	7
Publication status	Published - 1 Dec 2001
Externally published	Yes
Event	Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001) - , Brazil Duration: 17 Mar 2001 → 19 Mar 2001

Publication series

Name	Electronic Notes in Discrete Mathematics
Publisher	Elsevier
ISSN (Print)	1571-0653

Conference

Conference	Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001)
Country/Territory	Brazil
Period	17/03/01 → 19/03/01

ASJC Scopus subject areas

Discrete Mathematics and Combinatorics
Applied Mathematics

Cite this

@inproceedings{2ec5be64986c4f8bb84508b2babfe8a9,

title = "On the complexity of inferring rooted evolutionary trees",

abstract = "We prove that the maximum inferred local consensus tree problem is NP-complete, thus resolving an open question from [3].",

author = "Jansson, {Jesper Andreas}",

year = "2001",

month = dec,

day = "1",

language = "English",

volume = "7",

series = "Electronic Notes in Discrete Mathematics",

publisher = "Elsevier",

pages = "50--53",

editor = "Szwarcfiter, {Jayme Luiz}",

booktitle = "Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001)",

note = "Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001) ; Conference date: 17-03-2001 Through 19-03-2001",

}

On the complexity of inferring rooted evolutionary trees. / Jansson, Jesper Andreas.
Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001). ed. / Jayme Luiz Szwarcfiter. Vol. 7 2001. p. 50-53 (Electronic Notes in Discrete Mathematics).

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

TY - GEN

T1 - On the complexity of inferring rooted evolutionary trees

AU - Jansson, Jesper Andreas

PY - 2001/12/1

Y1 - 2001/12/1

N2 - We prove that the maximum inferred local consensus tree problem is NP-complete, thus resolving an open question from [3].

AB - We prove that the maximum inferred local consensus tree problem is NP-complete, thus resolving an open question from [3].

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

M3 - Conference article published in proceeding or book

VL - 7

T3 - Electronic Notes in Discrete Mathematics

SP - 50

EP - 53

BT - Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001)

A2 - Szwarcfiter, Jayme Luiz

T2 - Proceedings of the Brazilian Symposium on Graphs, Algorithms, and Combinatorics (GRACO 2001)

Y2 - 17 March 2001 through 19 March 2001

ER -

On the complexity of inferring rooted evolutionary trees

Abstract

Publication series

Conference

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this