Computing on a free tree via complexity-preserving mappings

DOI10.1007/BF01840366zbMath0636.68092MaRDI QIDQ1098314

Bernard Chazelle

Publication date: 1987

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

abstract data types; inverse Ackermann function; linear lists; free trees; query-answering

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68P05: Data structures

68P20: Information storage and retrieval of data

68R99: Discrete mathematics in relation to computer science

03D60: Computability and recursion theory on ordinals, admissible sets, etc.

Related Items

Shortcutting Planar Digraphs, Transitive-Closure Spanners: A Survey, Small hop-diameter sparse spanners for doubling metrics, Steiner transitive-closure spanners of low-dimensional posets, Efficient provably-secure hierarchical key assignment schemes, Visibility and intersection problems in plane geometry, Finding level-ancestors in trees, Reconstructing edge-disjoint paths., Parallel preprocessing for path queries without concurrent reading., Succinct representations of weighted trees supporting path queries, Building Cartesian trees from free trees with \(k\) leaves

Cites Work

• Unnamed Item
• Unnamed Item
• Multidimensional divide-and-conquer
• Fractional cascading. I: A data structuring technique
• A data structure for dynamic trees
• Applications of Path Compression on Balanced Trees
• Fast Algorithms for Finding Nearest Common Ancestors
• A new approach to rectangle intersections
• Priority Search Trees
• New Data Structures for Orthogonal Range Queries
• Self-adjusting binary search trees
• A unifying look at data structures
• Efficiency of a Good But Not Linear Set Union Algorithm