---
res:
  bibo_abstract:
  - "We are given a set T = {T 1 ,T 2 , . . .,T k } of rooted binary trees, each T
    i leaf-labeled by a subset L(Ti)⊂{1,2,...,n} . If T is a tree on {1,2, . . .,n
    }, we let T|L denote the minimal subtree of T induced by the nodes of L and all
    their ancestors. The consensus tree problem asks whether there exists a tree T
    * such that, for every i , T∗|L(Ti) is homeomorphic to T i .\r\n\r\nWe present
    algorithms which test if a given set of trees has a consensus tree and if so,
    construct one. The deterministic algorithm takes time min{O(N n 1/2 ), O(N+ n
    2 log n )}, where N=∑i|Ti| , and uses linear space. The randomized algorithm takes
    time O(N log3 n) and uses linear space. The previous best for this problem was
    a 1981 O(Nn) algorithm by Aho et al. Our faster deterministic algorithm uses a
    new efficient algorithm for the following interesting dynamic graph problem: Given
    a graph G with n nodes and m edges and a sequence of b batches of one or more
    edge deletions, then, after each batch, either find a new component that has just
    been created or determine that there is no such component. For this problem, we
    have a simple algorithm with running time O(n 2 log n + b 0 min{n 2 , m log n
    }), where b 0 is the number of batches which do not result in a new component.
    For our particular application, b0≤1 . If all edges are deleted, then the best
    previously known deterministic algorithm requires time O(mn−−√) to solve this
    problem. We also present two applications of these consensus tree algorithms which
    solve other problems in computational evolutionary biology.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: V.
      foaf_name: King, V.
      foaf_surname: King
  - foaf_Person:
      foaf_givenName: T.
      foaf_name: Warnow, T.
      foaf_surname: Warnow
  bibo_doi: 10.1007/pl00009268
  bibo_volume: 24
  dct_date: 1999^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/0178-4617
  - http://id.crossref.org/issn/1432-0541
  dct_language: eng
  dct_publisher: Springer Nature@
  dct_subject:
  - Algorithms
  - Data structures
  - Evolutionary biology
  - Theory of databases
  dct_title: Constructing a tree from homeomorphic subtrees, with applications to
    computational evolutionary biology@
...