Efficiency of a Good But Not Linear Set Union Algorithm

Cited In (only showing first 100 items - show all)

A survey of direct methods for sparse linear systems
Another variation on the common subexpression problem
Testing string superprimitivity in parallel
Upper and lower bounds for fully retroactive graph problems
Fast congruence closure and extensions
A complement to Tarjan's result about the lower bound on the complexity of the set union problem
A linear-time recognition algorithm for interval dags
Fast algorithms for testing unsatisfiability of ground Horn clauses with equations
A linear systolic algorithm for the connected component problem
Fast incremental planarity testing
On the relationship of congruence closure and unification
An inherently iterative computation of Ackermann's function
Unifications, deunifications, and their complexity
Simple and optimal output-sensitive construction of contour trees using monotone paths
Incremental DFA minimisation
On-line computation of transitive closures of graphs
Unique satisfiability of Horn sets can be solved in nearly linear time
Almost linear upper bounds on the length of general Davenport-Schinzel sequences
A simplified construction of nonlinear Davenport-Schinzel sequences
Dynamic orthogonal range queries in OLAP.
Maintaining bridge-connected and biconnected components on-line
A decomposition algorithm for nested resource allocation problems
Simpler proofs with decentralized invariants
Smallest \(k\)-enclosing rectangle revisited
Finding a feasible flow in a strongly connected network
Fast and Simple Algorithms for Weighted Perfect Matching
Thek best spanning arborescences of a network
On the row merge tree for sparse LU factorization with partial pivoting
High girth augmented trees are huge
A linear algorithm for the maximal planar subgraph problem
A fully dynamic reachability algorithm for directed graphs with an almost linear update time
On constructing the elimination tree
Linear expected time of a simple union-find algorithm
ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS
Salembier's min-tree algorithm turned into breadth first search
Title not available (Why is that?)
Most and least uniform spanning trees
Efficient region segmentation on compressed gray images using quadtree and shading representation
Worst-case analysis of the set-union problem with extended backtracking
Combination of convex theories: modularity, deduction completeness, and explanation
A partially persistent data structure for the set-union problem
A note on data structures for maintaining bipartitions
Representing Interpolant Topology for Contour Tree Computation
Maintenance of 2- and 3-edge-connected components of graphs. I
Using bisimulation proof techniques for the analysis of distributed abstract machines
The set union problem with dynamic weighted backtracking
An \(O(EV\log^2V)\) algorithm for the maximal flow problem
Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits
Exact and approximate truthful mechanisms for the shortest paths tree problem
Two linear time Union--Find strategies for image processing
Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space
On updating the structure of sparse matrix factors
Amortized Computational Complexity
A note on set union with arbitrary deunions
Extremal problems for colored trees and Davenport-Schinzel sequences
Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor
Finding dominators via disjoint set union
Power domination in circular-arc graphs
Fast algorithms for the undirected negative cost cycle detection problem
A linear algorithm for MLL proof net correctness and sequentialization
New constructions for provably-secure time-bound hierarchical key assignment schemes
Fast reoptimization for the minimum spanning tree problem
A note on Arc tolerances in sparse shortest-path and network flow problems
Design and implementation of an efficient priority queue
First Results for 3D Image Segmentation with Topological Map
Unification theory
Strong articulation points and strong bridges in large scale graphs
A polynomial time algorithm for finding the prime factors of Cartesian- product graphs
Computing on a free tree via complexity-preserving mappings
A simple and efficient union-find-delete algorithm
Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
A tight lower bound for top-down skew heaps
Minimization of finite state automata through partition aggregation
An \(O(n^2)\) algorithm for computing optimal continuous voltage schedules
Generalized Davenport-Schinzel sequences with linear upper bound
A state-of-the-art review of parallel-machine scheduling research
Linear-space S-table algorithms for the longest common subsequence problem
A linear-time algorithm for a special case of disjoint set union
Finding the most vital node of a shortest path.
Aggregation-based minimization of finite state automata
Path-based depth-first search for strong and biconnected components
Edge-disjoint spanning trees and depth-first search
2-vertex connectivity in directed graphs
A data structure for dynamic trees
On the \(k\)-coloring of intervals
Linear unification
Max-coloring paths: tight bounds and extensions
Unification problems with one-sided distributivity
A topological approach to dynamic graph connectivity
Quasi-optimal range searching in spaces of finite VC-dimension
On the bicriterion - minimal cost/minimal label - spanning tree problem
Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
Machine-checked verification of the correctness and amortized complexity of an efficient union-find implementation
Partition refinement techniques: an interesting algorithmic tool kit
The saga of minimum spanning trees
Practical and efficient split decomposition via graph-labelled trees
A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm
The general maximum matching algorithm of Micali and Vazirani
Lexicographic permutations with restrictions
Dynamic matchings in left vertex weighted convex bipartite graphs

This page was built for publication: Efficiency of a Good But Not Linear Set Union Algorithm

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