Your browser does not fully support modern features. Please upgrade for a smoother experience.
Submitted Successfully!
+1 credit
Thank you for your contribution! You can also upload a video entry or images related to this topic.
For video creation, please contact our Academic Video Service.
| Version | Summary | Created by | Modification | Content Size | Created at | Operation |
|---|---|---|---|---|---|---|
| 1 | Vivi Li | -- | 1656 | 2022-11-16 01:40:51 |
Video Upload Options
We provide professional Academic Video Service to translate complex research into visually appealing presentations. Would you like to try it?
Cite
If you have any further questions, please contact Encyclopedia Editorial Office.
HandWiki. Parallel Tree Contraction. Encyclopedia. Available online: https://encyclopedia.pub/entry/34835 (accessed on 23 September 2026).
HandWiki. Parallel Tree Contraction. Encyclopedia. Available at: https://encyclopedia.pub/entry/34835. Accessed September 23, 2026.
HandWiki. "Parallel Tree Contraction" Encyclopedia, https://encyclopedia.pub/entry/34835 (accessed September 23, 2026).
HandWiki. (2022, November 16). Parallel Tree Contraction. In Encyclopedia. https://encyclopedia.pub/entry/34835
HandWiki. "Parallel Tree Contraction." Encyclopedia. Web. 16 November, 2022.
Copy Citation
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. This article hereby focuses on a particular solution, which is a variant of the algorithm by Miller and Reif, and its application.
planar graph
algorithm
application
References
- Gary L. Miller and John H. Reif, Parallel Tree Contraction--Part I: Fundamentals., 1989
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN:0-262-03293-7 . Section 10.4: Representing rooted trees, pp. 214–217. Chapters 12–14 (Binary Search Trees, Red-Black Trees, Augmenting Data Structures), pp. 253–320.
- Donald Knuth. The Art of Computer Programming: Fundamental Algorithms, Third Edition. Addison-Wesley, 1997. ISBN:0-201-89683-4 . Section 2.3: Trees, pp. 308–423.
- "Chapter 6. Bounded height trees and tree-depth", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics, 28, Heidelberg: Springer, 2012, pp. 115–144, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7 . https://dx.doi.org/10.1007%2F978-3-642-27875-4
- Andrew Goldberg, Serge Plotkin, and Gregory Shannon, Parallel symmetry-breaking in sparse graphs, Proceedings of the nineteenth annual ACM symposium on Theory of computing (ACM), 1987
- Euler tour trees - in Lecture Notes in Advanced Data Structures. Prof. Erik Demaine; Scribe: Katherine Lai. http://courses.csail.mit.edu/6.851/spring07/scribe/lec05.pdf
- Gary L. Miller and John H. Reif, Parallel tree contraction and its application, Defense Technical Information Center, 1985
- Parallel Algorithms: Tree Operations, Guy Blelloch, Carnegie Mellon University, 2009 https://www.cs.cmu.edu/afs/cs/academic/class/15499-s09/www/scribe/lec11/lec11.pdf
- MORIHATA, Akimasa, and Kiminori MATSUZAKI, A Parallel Tree Contraction Algorithm on Non-Binary Trees, MATHEMATICAL ENGINEERING TECHNICAL REPORTS, 2008
- Parallel Algorithms: Analyzing Parallel Tree Contraction, Guy Blelloch, 2007 https://www.cs.cmu.edu/afs/cs/academic/class/15492-f07/www/scribe/lec9/lecture9.pdf
- S Buss, Algorithms for boolean formula evaluation and for tree contraction, Arithmetic, Proof Theory, and Computational Complexity, 1993, pp. 96-115
- Bader, David A., Sukanya Sreshta, and Nina R. Weisse-Bernstein, Evaluating arithmetic expressions using tree contraction: A fast and scalable parallel implementation for symmetric multiprocessors (SMPs), High Performance Computing—HiPC 2002. Springer Berlin Heidelberg, 2002, pp. 63-75.
- Applications of Parallel Tree Contraction, Samuel Yeom, 2015 http://math.mit.edu/~rpeng/18434/applicationsParallelTreeContraction.pdf
More
Information
Subjects:
Others
Contributor
MDPI registered users' name will be linked to their SciProfiles pages. To register with us, please refer to https://encyclopedia.pub/register
:
View Times:
692
Entry Collection:
HandWiki
Revision:
1 time
(View History)
Update Date:
16 Nov 2022
Table of Contents
Notice
You are not a member of the advisory board for this topic. If you want to update advisory board member profile, please contact office@encyclopedia.pub.
OK
Confirm
Only members of the Encyclopedia advisory board for this topic are allowed to note entries. Would you like to become an advisory board member of the Encyclopedia?
Yes
No
${ textCharacter }/${ maxCharacter }
Submit
Cancel
Back
Comments
${ item }
|
${ item.createdUser.fullName }
${ item.createdAt }
${ item.vote }
${ item.reply }
Delete
${ reply.createdUser.fullName }
${ reply.createdAt }
${ reply.vote }
Delete
There is no reply to this comment~
${ item.replyTextCharacter }/${ item.replyMaxCharacter }
Submit
Cancel
More
No more~
There is no comment~
${ textCharacter }/${ maxCharacter }
Submit
Cancel
${ selectedItem.replyTextCharacter }/${ selectedItem.replyMaxCharacter }
Submit
Cancel
Confirm
Are you sure to Delete?
Yes
No