Applications of Path Compression on Balanced Trees
From MaRDI portal
Publication:3048273
DOI10.1145/322154.322161zbMath0413.68063OpenAlexW2023658462WikidataQ56209648 ScholiaQ56209648MaRDI QIDQ3048273
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322154.322161
computational complexitygraph algorithmminimum spanning treeundirected graphbalanced treespath compressionfunctional inverse of Ackermann's functiondominators in a flow graph
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Strong articulation points and strong bridges in large scale graphs, A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges, Optimal parallel verification of minimum spanning trees in logarithmic time, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, An optimal EREW PRAM algorithm for minimum spanning tree verification, Faster algorithms for finding lowest common ancestors in directed acyclic graphs, Optimal pointer algorithms for finding nearest common ancestors in dynamic trees, Finding the k smallest spanning trees, Computing on a free tree via complexity-preserving mappings, A simpler minimum spanning tree verification algorithm, Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems, Tight bounds for distributed minimum-weight spanning tree verification, Finding dominators via disjoint set union, Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs, A weight-scaling algorithm for \(f\)-factors of multigraphs, Faster swap edge computation in minimum diameter spanning trees, A Path Cover Technique for LCAs in Dags, Computing all the best swap edges distributively, Properties of data flow frameworks: A unified model, A dual ascent algorithm for the 1-tree relaxation of the symmetric traveling salesman problem, Distributed verification of minimum spanning trees, The saga of minimum spanning trees, The tree longest detour problem in a biconnected graph., Path Minima in Incremental Unrooted Trees, Improved filtering for weighted circuit constraints, Memory-efficient fixpoint computation, Fast and compact self-stabilizing verification, computation, and fault detection of an MST, Finding the \(k\) smallest spanning trees, A \(\min\)-\(\max\) relation in flowgraphs and some applications, Parallel search algorithms for graphs and trees, Efficient determination of the \(k\) most vital edges for the minimum spanning tree problem, Faster algorithm to find anti-risk path between two nodes of an undirected graph, Improved algorithms for the Steiner problem in networks, A simpler minimum spanning tree verification algorithm, A fast and simple Steiner routing heuristic, Approximate string matching on Ziv--Lempel compressed text, Optimal binary trees with order constraints, A data structure for dynamic trees, A new algorithm for the minimum spanning tree verification problem, A linear-time algorithm for a special case of disjoint set union, Efficient algorithms for finding the most vital edge of a minimum spanning tree, Linear verification for spanning trees, A faster computation of the most vital edge of a shortest path, Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗, Linear-Time Algorithm for Long LCF with k Mismatches, A linear algorithm for analysis of minimum spanning and shortest-path trees of planar graphs
