@techreport{TR-IC-03-26,
  number = {IC-03-26},
  author = {Guilherme P. Telles and João Meidanis},
  title = {Building {PQR} Trees in Almost-Linear Time},
  month = {November},
  year = {2003}, 
  institution = {Institute of Computing, University of Campinas},
  note = {In English, 13 pages.
    \par\selectlanguage{english}\textbf{Abstract}
       In 1976, Booth and Leuker invented the PQ trees as a compact
       way of storing and manipulating all the permutations on $n$
       elements that keep consecutive the elements in certain given
       sets $C_1, C_2, \ldots, C_m$. This problem finds applications
       in DNA physical mapping, interval graph recognition, logic
       circuit optimization and data retrieval, for instance. In 1995,
       Meidanis and Munuera created the PQR trees, a natural
       generalization of PQ trees.  The difference between them is
       that PQR trees exist for every set collection, even when there
       are no valid permutations.  The R nodes encapsulate subsets
       where the consecutive ones property fails.  In this note we
       present an almost-linear time algorithm to build a PQR tree for
       an arbitrary set collection.
  }
}