Polynomialtime algorithms for the ordered maximum agreement subtree problem
(2004) 15th Annual Symposium, CPM 2004 In Combinatorial pattern matching / Lecture notes in computer science 3109. p.220229 Abstract
 For a set of rooted, unordered, distinctly leaflabeled trees, the NPhard maximum agreement subtree problem (MAST) asks for a tree contained (up to isomorphism. or homeomorphism) in all of the input trees with as many labeled leaves as possible. We study the ordered variants of MAST where the trees are uniformly or nonuniformly ordered. We provide the first known polynomialtime algorithms for the uniformly and nonuniformly ordered homeomorphic variants as well as the uniformly and nonuniformly ordered isomorphic variants of MAST. Our algorithms run in time O(kn(3)), O(n(3) min{nk, n + log (k>1) n}), O(kn(3)), and O((k + n)n(3)), respectively, where n is the number of leaf labels and k is the number of input trees.
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/272539
 author
 Dessmark, Anders ^{LU} ; Jansson, Jesper ^{LU} ; Lingas, Andrzej ^{LU} and Lundell, EvaMarta ^{LU}
 organization
 publishing date
 2004
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 in
 Combinatorial pattern matching / Lecture notes in computer science
 volume
 3109
 pages
 220  229
 publisher
 Springer
 conference name
 15th Annual Symposium, CPM 2004
 external identifiers

 wos:000222627600016
 scopus:34547253932
 ISSN
 03029743
 16113349
 ISBN
 354022341X
 DOI
 10.1007/s0045300700809
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 6d5801f3076643cc96b0b4b45e3cede6 (old id 272539)
 date added to LUP
 20071023 13:36:33
 date last changed
 20170101 05:09:45
@inproceedings{6d5801f3076643cc96b0b4b45e3cede6, abstract = {For a set of rooted, unordered, distinctly leaflabeled trees, the NPhard maximum agreement subtree problem (MAST) asks for a tree contained (up to isomorphism. or homeomorphism) in all of the input trees with as many labeled leaves as possible. We study the ordered variants of MAST where the trees are uniformly or nonuniformly ordered. We provide the first known polynomialtime algorithms for the uniformly and nonuniformly ordered homeomorphic variants as well as the uniformly and nonuniformly ordered isomorphic variants of MAST. Our algorithms run in time O(kn(3)), O(n(3) min{nk, n + log (k>1) n}), O(kn(3)), and O((k + n)n(3)), respectively, where n is the number of leaf labels and k is the number of input trees.}, author = {Dessmark, Anders and Jansson, Jesper and Lingas, Andrzej and Lundell, EvaMarta}, booktitle = {Combinatorial pattern matching / Lecture notes in computer science}, isbn = {354022341X}, issn = {03029743}, language = {eng}, pages = {220229}, publisher = {Springer}, title = {Polynomialtime algorithms for the ordered maximum agreement subtree problem}, url = {http://dx.doi.org/10.1007/s0045300700809}, volume = {3109}, year = {2004}, }