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 typesinverse Ackermann functionlinear listsfree treesquery-answering

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Information storage and retrieval of data (68P20) Discrete mathematics in relation to computer science (68R99) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)

Related Items (26)

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

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

This page was built for publication: Computing on a free tree via complexity-preserving mappings