page_title: Tree contraction
section_title: Definitions
hierarchical_section_title: Tree contraction / Definitions
caption_attribution_description: English: rake
context_page_description: In computer science, parallel tree contraction is a broadly applicable technique for the parallel solution of a large number of tree problems, and is used as an algorithm design technique for the design of a large number of parallel graph algorithms. Parallel tree contraction was introduced by Gary L. Miller and John H. Reif, and has subsequently been modified to improve efficiency by X. He and Y. Yesha, Hillel Gazit, Gary L. Miller and Shang-Hua Teng and many others.
  Tree contraction has been used in designing many efficient parallel algorithms, including expression evaluation, finding lowest common ancestors, tree isomorphism, graph isomorphism, maximal subtree isomorphism, common subexpression elimination, computing the 3-connected components of a graph, and finding an explicit planar embedding of a planar graph
  Based on the research and work on parallel tree contraction, various algorithms have been proposed targeting to improve the efficiency or simplicity of this topic.
context_section_description: Before going into the algorithm itself, we first look at a few terminologies that will be used later.
  Rake – Rake step joins every left leaf of binary nodes to the parent. By join, we mean that it undergoes a functional process which achieves the operation we want to make. An example of rake is given in Figure 1.
  Compress – Compress step is actually a sequence of several events: (1) Find an independent set of unary nodes. (Independence here is defined such that no two are neighbors, meaning no parent to child relation) (2) Join each node in independent set with its child (Note that independent set is not unique). An example of compress is given in Figure 2.
  And in order to solve actual problems using tree contraction, the algorithm has a structure:
  Repeat until tree becomes a unary node
  {
      Rake;
      Compress;
  }
caption: Fig. 1: Rake Operation
exif: {}