Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips
This paper is about an application of the mathematics of the zip, reduce (fold) and accumulate (scan) operations on lists. It gives an account of the derivation of a linear-time breadth-first tree traversal algorithm, and of a subtle and efficient breadth-first tree labelling algorithm.
| Main Authors: | , |
|---|---|
| Format: | Report |
| Published: |
Dept of Computer Science‚ University of Auckland
1993
|
| _version_ | 1826305358375682048 |
|---|---|
| author | Jones, G Gibbons, J |
| author_facet | Jones, G Gibbons, J |
| author_sort | Jones, G |
| collection | OXFORD |
| description | This paper is about an application of the mathematics of the zip, reduce (fold) and accumulate (scan) operations on lists. It gives an account of the derivation of a linear-time breadth-first tree traversal algorithm, and of a subtle and efficient breadth-first tree labelling algorithm. |
| first_indexed | 2024-03-07T06:31:41Z |
| format | Report |
| id | oxford-uuid:f6313e89-7373-49b5-a65c-b29d43d18ec5 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T06:31:41Z |
| publishDate | 1993 |
| publisher | Dept of Computer Science‚ University of Auckland |
| record_format | dspace |
| spelling | oxford-uuid:f6313e89-7373-49b5-a65c-b29d43d18ec52022-03-27T12:33:16ZLinear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and ZipsReporthttp://purl.org/coar/resource_type/c_93fcuuid:f6313e89-7373-49b5-a65c-b29d43d18ec5Department of Computer ScienceDept of Computer Science‚ University of Auckland1993Jones, GGibbons, JThis paper is about an application of the mathematics of the zip, reduce (fold) and accumulate (scan) operations on lists. It gives an account of the derivation of a linear-time breadth-first tree traversal algorithm, and of a subtle and efficient breadth-first tree labelling algorithm. |
| spellingShingle | Jones, G Gibbons, J Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips |
| title | Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips |
| title_full | Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips |
| title_fullStr | Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips |
| title_full_unstemmed | Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips |
| title_short | Linear−time Breadth−first Tree Algorithms: An Exercise in the Arithmetic of Folds and Zips |
| title_sort | linear time breadth first tree algorithms an exercise in the arithmetic of folds and zips |
| work_keys_str_mv | AT jonesg lineartimebreadthfirsttreealgorithmsanexerciseinthearithmeticoffoldsandzips AT gibbonsj lineartimebreadthfirsttreealgorithmsanexerciseinthearithmeticoffoldsandzips |