A Data Structure for Dynamically Maintaining Rooted Trees

DOI10.1006/JAGM.1996.0835MaRDI QIDQ4349698zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

directed topology tree data structure

Mathematics Subject Classification ID

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

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

Cited in

(20)

• scientific article; zbMATH DE number 4011953 (Why is no real title available?)
• 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
• LS(graph): a constraint-based local search for constraint optimization on trees and paths
• Dynamic trees in practice
• Dynamizing static algorithms, with applications to dynamic trees and history independence
• Topology B-trees and their applications
• scientific article; zbMATH DE number 437542 (Why is no real title available?)
• 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
• Self-adjusting top trees
• Fast and simple unrooted dynamic forests

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)