Efficiency of a Good But Not Linear Set Union Algorithm

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

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
\(P_ 4\)-trees and substitution decomposition
Practical and efficient circle graph recognition
Oriented Euler complexes and signed perfect matchings
Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits
A practical unification algorithm
Learning deterministic even linear languages from positive examples
Equistable simplicial, very well-covered, and line graphs
Approximate range searching: The absolute model
Finding an anti-risk path between two nodes in undirected graphs
Extending common intervals searching from permutations to sequences
Fast sequential importance sampling to estimate the graph reliability polynomial
Satisfiability modulo theories
Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs.
An augmenting path algorithm for linear matroid parity
A practically efficient and almost linear unification algorithm
An efficient PQ-graph algorithm for solving the graph-realization problem
Multivariate topology simplification
Path problems in skew-symmetric graphs
A fully dynamic graph algorithm for recognizing interval graphs
Testing flow graph reducibility
Computing contour trees in all dimensions
Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree
An efficient abstract machine for safe ambients
Proof of a conjecture of Erdős and Turán
An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree
A faster computation of the most vital edge of a shortest path
A new algorithm for the minimum spanning tree verification problem
A 0.5358-approximation for Bandpass-2
Finding optimum branchings
Shortcutting directed and undirected networks with a degree constraint
A coherent logic based geometry theorem prover capable of producing formal and readable proofs
Linear time analysis of properties of conflict-free and general Petri nets
A fast algorithm for constructing a tree automaton recognizing a congruential tree language
Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
A class of algorithms which require nonlinear time to maintain disjoint sets
Shortcutting Planar Digraphs
Finding the most vital edge with respect to minimum spanning tree in weighted graphs
Faster graph bipartization
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

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)