A data structure for dynamic trees

DOI10.1016/0022-0000(83)90006-5zbMath0509.68058DBLPjournals/jcss/SleatorT83OpenAlexW2018804864WikidataQ56018634 ScholiaQ56018634MaRDI QIDQ1838310

Yanyan Li

Publication date: 1983

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(83)90006-5

zbMATH Keywords

constrained minimum spanning trees nearest common ancestors vertex-disjoint trees

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10)

Related Items (only showing first 100 items - show all)

Matching games with partial information ⋮ Tight bounds for conflict-free chromatic guarding of orthogonal art galleries ⋮ Scaling algorithms for network problems ⋮ Complexity models for incremental computation ⋮ Partial inverse min-max spanning tree problem ⋮ Dynamic suffix tree and two-dimensional texts management ⋮ Document retrieval with one wildcard ⋮ Dynamic dictionary matching ⋮ Tight bounds for online weighted tree augmentation ⋮ Upper and lower bounds for fully retroactive graph problems ⋮ Routing on heavy-path WSPD-spanners ⋮ A generalization of the scaling max-flow algorithm ⋮ Reporting consecutive substring occurrences under bounded gap constraints ⋮ On-line updating of solutions to a class of matroid intersection problems ⋮ Less space: indexing for queries with wildcards ⋮ Fully dynamic biconnectivity in graphs ⋮ Dynamic expression trees ⋮ Categorified Reeb graphs ⋮ A complexity analysis and an algorithmic approach to student sectioning in existing timetables ⋮ Computing on a free tree via complexity-preserving mappings ⋮ A note on finding compact sets in graphs represented by an adjacency list ⋮ A faster algorithm for computing the principal sequence of partitions of a graph ⋮ On finding most uniform spanning trees ⋮ Linear-size nonobtuse triangulation of polygons ⋮ On the efficiency of maximum-flow algorithms on networks with small integer capacities ⋮ Compact separator decompositions in dynamic trees and applications to labeling schemes ⋮ Finding paths and deleting edges in directed acyclic graphs ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Algorithms for multicommodity flows in planar graphs ⋮ Average case analysis of dynamic geometric optimization ⋮ A multifacility location problem on median spaces ⋮ A decentralized flow redistribution algorithm for avoiding cascaded failures in complex networks ⋮ Maximum \((s,t)\)-flows in planar networks in \(\mathcal O(|V| \log |V|)\) time ⋮ A fast scaling algorithm for the weighted triangle-free 2-matching problem ⋮ Reoptimization of maximum weight induced hereditary subgraph problems ⋮ Drawing \(c\)-planar biconnected clustered graphs ⋮ Matching a set of strings with variable length don't cares ⋮ Incremental Voronoi diagrams ⋮ Avoiding the global sort: a faster contour tree algorithm ⋮ Dynamic planar embeddings of dynamic graphs ⋮ Linear-time construction of two-dimensional suffix trees ⋮ Maximum flow in directed planar graphs with vertex capacities ⋮ Sorting signed permutations by reversals using link-cut trees ⋮ An \(O(m(m+n\log {n})\log(nC))\)-time algorithm to solve the minimum cost tension problem ⋮ Dynamic maintenance of directed hypergraphs ⋮ Dictionary matching with a bounded gap in pattern or in text ⋮ Generating pseudo-random permutations and maximum flow algorithms ⋮ On maximum flows in polyhedral domains ⋮ The saga of minimum spanning trees ⋮ An \(O(mn \log (nU))\) time algorithm to solve the feasibility problem ⋮ Efficient algorithms for computing Reeb graphs ⋮ An efficient scaling algorithm for the minimum weight bibranching problem ⋮ Dynamic algorithms for monotonic interval scheduling problem ⋮ Use of dynamic trees in a network simplex algorithm for the maximum flow problem ⋮ Maintaining centdians in a fully dynamic forest with top trees ⋮ LS(graph): a constraint-based local search for constraint optimization on trees and paths ⋮ An efficient strongly connected components algorithm in the fault tolerant model ⋮ Engineering a combinatorial Laplacian solver: lessons learned ⋮ Finding minimum-cost flows by double scaling ⋮ Maintaining bridge-connected and biconnected components on-line ⋮ Forests, frames, and games: Algorithms for matroid sums and applications ⋮ Dynamic and static algorithms for optimal placement of resources in a tree ⋮ About the minimum mean cycle-canceling algorithm ⋮ Shortest augmenting paths for online matchings on trees ⋮ On the computational behavior of a polynomial-time network flow algorithm ⋮ Compressed subsequence matching and packed tree coloring ⋮ A new Karzanov-type \(O(n^ 3)\) max-flow algorithm ⋮ Transitions in geometric minimum spanning trees ⋮ A genuinely polynomial primal simplex algorithm for the assignment problem ⋮ Parallel methods for visibility and shortest-path problems in simple polygons ⋮ Data structures for halfplane proximity queries and incremental Voronoi diagrams ⋮ On Cartesian trees and range minimum queries ⋮ Maintaining dynamic minimum spanning trees: an experimental study ⋮ Confluently persistent tries for efficient version control ⋮ Efficient authenticated data structures for graph connectivity and geometric search problems ⋮ Fast reoptimization for the minimum spanning tree problem ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ A faster algorithm for matching a set of patterns with variable length don't cares ⋮ Reconstructing edge-disjoint paths faster ⋮ Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals ⋮ \(\log\)-lists and their applications to sorting by transpositions, reversals and block-interchanges ⋮ Local search for the Steiner tree problem in the Euclidean plane ⋮ Dynamic mechanism design ⋮ A parallel algorithm for finding a blocking flow in an acyclic network ⋮ A primal simplex algorithm that solves the maximum flow problem in at most nm pivots and \(O(n^ 2m)\) time ⋮ An \(O(m\log n)\) algorithm for the max+sum spanning tree problem ⋮ Improved algorithms for the multicut and multiflow problems in rooted trees ⋮ Labelled trees and pairs of input--output permutations in priority queues ⋮ The nearest common ancestor in a dynamic tree ⋮ Computational investigations of maximum flow algorithms ⋮ Properties of Gomory-Hu co-cycle bases ⋮ Diagnosing infeasibilities in network flow problems ⋮ On indexed data broadcast ⋮ Two flow network simplification algorithms ⋮ Tree path majority data structures ⋮ Incremental convex planarity testing ⋮ New labeling procedures for the basis graph in generalized networks ⋮ Network flow and 2-satisfiability ⋮ The maximum flow problem: A max-preflow approach ⋮ Linear-space data structures for range frequency queries on arrays and trees

Cites Work

This page was built for publication: A data structure for dynamic trees