A Data Structure for Dynamically Maintaining Rooted Trees

DOI10.1006/JAGM.1996.0835zbMATH Open0882.68104OpenAlexW2025791989MaRDI QIDQ4349698FDOQ4349698

Authors: Greg N. Frederickson 

Publication date: 25 August 1997

Published in: Journal of Algorithms (Search for Journal in Brave)

Full work available at URL: https://docs.lib.purdue.edu/cgi/viewcontent.cgi?article=1986&context=cstech

Recommendations

• scientific article; zbMATH DE number 437542
• Dynamic trees in practice
• Self-adjusting top trees
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Maintaining regular properties dynamically in \(k\)-terminal graphs

zbMATH Keywords

directed topology tree data structure

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Cited In (20)

• Title not available (Why is that?)
• Algorithms and Computation
• Succinct indices for path minimum, with applications
• Linear-space approximate distance oracles for planar, bounded-genus and minor-free graphs
• Pruning spanners and constructing well-separated pair decompositions in the presence of memory hierarchies
• \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges
• Power balance and apportionment algorithms for the United States Congress
• Dynamic tree shortcut with constant degree
• Dynamic path queries in linear space
• Dynamic trees in practice
• LS(graph): a constraint-based local search for constraint optimization on trees and paths
• Dynamizing static algorithms, with applications to dynamic trees and history independence
• Topology B-trees and their applications
• Title not available (Why is that?)
• Data structures for mergeable trees
• A consistent semantics of self-adjusting computation
• Incremental dead state detection in logarithmic time
• Union-copy structures and dynamic segment trees
• Fast and simple unrooted dynamic forests
• Self-adjusting top trees

This page was built for publication: A Data Structure for Dynamically Maintaining Rooted Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4349698)