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

Dynamic algorithms for graphs of bounded treewidth, Minimum Cuts and Sparsification in Hypergraphs, A Hierarchy of Lower Bounds for Sublinear Additive Spanners, Shortest path queries in digraphs of small treewidth, Shortcutting Planar Digraphs, Transitive-Closure Spanners: A Survey, Faster algorithms for shortest path and network flow based on graph decomposition, Small hop-diameter sparse spanners for doubling metrics, Steiner transitive-closure spanners of low-dimensional posets, Shortcutting directed and undirected networks with a degree constraint, Efficient provably-secure hierarchical key assignment schemes, Visibility and intersection problems in plane geometry, Finding level-ancestors in trees, Reconstructing edge-disjoint paths., Reconstructing edge-disjoint paths faster, Dynamic path queries in linear space, Parallel preprocessing for path queries without concurrent reading., Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree, Succinct indices for path minimum, with applications, Succinct representations of weighted trees supporting path queries, Building Cartesian trees from free trees with \(k\) leaves, Dynamic Tree Shortcut with Constant Degree, Simple Parallel Algorithms for Dynamic Range Products

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