Efficiency of a Good But Not Linear Set Union Algorithm
From MaRDI portal
Publication:4065031
DOI10.1145/321879.321884zbMath0307.68029OpenAlexW1986022261WikidataQ55953237 ScholiaQ55953237MaRDI QIDQ4065031
Publication date: 1975
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/5942
Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01) Algorithms in computer science (68W99)
Related Items
A feasibility study for a persistent homology-based \(k\)-nearest neighbor search algorithm in melanoma detection, Memory management for Union-Find algorithms, Proximity Search for Maximal Subgraph Enumeration, Finding Articulation Points of Large Graphs in Linear Time, Three Generalizations of Davenport--Schinzel Sequences, Some results of the relocation problems with processing times and deadlines, Lazy structure sharing for query optimization, Satisfiability Modulo Theories, On the \(k\)-coloring of intervals, Unique satisfiability of Horn sets can be solved in nearly linear time, A linear algorithm for the maximal planar subgraph problem, Faster enumeration of all spanning trees of a directed graph, Bipartite completion of colored graphs avoiding chordless cycles of given lengths, Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor, Approximate generalized matching: \(f\)-matchings and \(f\)-edge covers, Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems, On the gold standard for security of universal steganography, Amortized Computational Complexity, Using topological sweep to extract the boundaries of regions in maps represented by region quadtrees, Dynamic Tree Shortcut with Constant Degree, On the bicriterion - minimal cost/minimal label - spanning tree problem, A partially persistent data structure for the set-union problem, Estimation of level set trees using adaptive partitions, A Branch-and-Price Framework for Decomposing Graphs into Relaxed Cliques, Four Soviets walk the dog: improved bounds for computing the Fréchet distance, Machine-Checked Verification of the Correctness and Amortized Complexity of an Efficient Union-Find Implementation, Primitives for asynchronous list compression, LZRR: LZ77 parsing with right reference, Recognizing union-find trees is NP-complete, An asymmetric multi-item auction with quantity discounts applied to Internet service procurement in Buenos Aires public schools, On the probabilistic min spanning tree problem, Strong Connectivity in Directed Graphs under Failures, with Applications, Power domination in circular-arc graphs, Optimal decremental connectivity in planar graphs, Shortcutting Planar Digraphs, Faster cut sparsification of weighted graphs, Improved bounds for finger search on a RAM, A fully dynamic graph algorithm for recognizing interval graphs, Efficient data race detection for async-finish parallelism, Critical sets in discrete Morse theories: relating Forman and piecewise-linear approaches, Equistable simplicial, very well-covered, and line graphs, An $$O(n^2)$$ Algorithm for Computing Optimal Continuous Voltage Schedules, Conditional congruence closure over uninterpreted and interpreted symbols, Path constraints in semistructured data, Exact and approximate truthful mechanisms for the shortest paths tree problem, Hierarchizing graph-based image segmentation algorithms relying on region dissimilarity: the case of the Felzenszwalb-Huttenlocher method, Unnamed Item, Provably Robust Simplification of Component Trees of Multidimensional Images, Combinatorial Maps for 2D and 3D Image Segmentation, Finding the gapped longest common subsequence by incremental suffix maximum queries, Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree, Efficient region segmentation on compressed gray images using quadtree and shading representation, OPTIMAL RANGE MAX DATACUBE FOR FIXED DIMENSIONS, Design and implementation of an efficient priority queue, Matching and spanning in certain planar graphs, Approximate range searching: The absolute model, Fast connected-component labeling, Pyramid segmentation algorithms revisited, Unnamed Item, The degree-preserving spanning tree problem in strongly chordal and directed path graphs, Finding optimum branchings, Bisimulation and coinduction enhancements: a historical perspective, Thek best spanning arborescences of a network, Aggregation-based minimization of finite state automata, Dynamic interpolation search revisited, Incremental DFA Minimisation, On the König deficiency of zero-reducible graphs, Simpler proofs with decentralized invariants, A Fully Dynamic Reachability Algorithm for Directed Graphs with an Almost Linear Update Time, Smallest \(k\)-enclosing rectangle revisited, A Decomposition Algorithm for Nested Resource Allocation Problems, Fast algorithms for convex cost flow problems on circles, lines, and trees, Algebraic Bayesian networks: checking backbone connectivity, Representing Interpolant Topology for Contour Tree Computation, Unnamed Item, Faster graph bipartization, A Compact Representation for Syntactic Dependencies in QBFs, Design and Engineering of External Memory Traversal Algorithms for General Graphs, Depth First Search in the Semi-streaming Model, Smallest k-enclosing rectangle revisited, Concurrent disjoint set union, Parameterized Complexity of Discrete Morse Theory, A Parallel Edge Orientation Algorithm for Quadrilateral Meshes, Quasi-optimal range searching in spaces of finite VC-dimension, A Coherent Logic Based Geometry Theorem Prover Capable of Producing Formal and Readable Proofs, Solving some combinatorial problems on arrays with one-way dataflow, Constructing light spanners deterministically in near-linear time, Path problems in skew-symmetric graphs, A note on Arc tolerances in sparse shortest-path and network flow problems, A data structure for dynamic trees, Comparative study and proof of single-pass connected components algorithms, Source-tracking unification, Oriented Euler complexes and signed perfect matchings, A new algorithm for the minimum spanning tree verification problem, Parallel preprocessing for path queries without concurrent reading., ALGORITHMS FOR K-DISJOINT MAXIMUM SUBARRAYS, Fast and Simple Algorithms for Weighted Perfect Matching, A parallel algorithm for generating multiple ordering spanning trees in undirected weighted graphs, The Inverse of Ackermann Function is Computable in Linear Time, Computing contour trees in all dimensions, Processing an Offline Insertion-Query Sequence with Applications, Learning strongly deterministic even linear languages from positive examples, Almost tightly-secure re-randomizable and replayable CCA-secure public key encryption, Linear-space S-table algorithms for the longest common subsequence problem, Unnamed Item, Flexible Fiber Surfaces: A Reeb-Free Approach, Coinductive Algorithms for Büchi Automata, Unification theory, Small hop-diameter sparse spanners for doubling metrics, Efficiently Representing Existential Dependency Sets for Expansion-based QBF Solvers, Minimization of Finite State Automata Through Partition Aggregation, A survey of direct methods for sparse linear systems, Automata-driven efficient subterm unification, On updating the structure of sparse matrix factors, Fast incremental planarity testing, Recognizing Union-Find Trees is NP-Complete, Even Without Rank Info, First Results for 3D Image Segmentation with Topological Map, Minimal Component-Hypertrees, PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT, W-Structures in Contour Trees, Short and Simple Cycle Separators in Planar Graphs, Strong articulation points and strong bridges in large scale graphs, A tight lower bound for top-down skew heaps, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs, Upper and lower bounds for fully retroactive graph problems, Most and least uniform spanning trees, An augmenting path algorithm for linear matroid parity, Path-based depth-first search for strong and biconnected components, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes, Almost linear upper bounds on the length of general Davenport-Schinzel sequences, Circular convex bipartite graphs: Maximum matching and Hamiltonian circuits, Computing on a free tree via complexity-preserving mappings, 2-vertex connectivity in directed graphs, Unification problems with one-sided distributivity, Fast algorithms for testing unsatisfiability of ground Horn clauses with equations, Dynamic matchings in left vertex weighted convex bipartite graphs, A practically efficient and almost linear unification algorithm, The general maximum matching algorithm of Micali and Vazirani, An inherently iterative computation of Ackermann's function, A topological approach to dynamic graph connectivity, Multivariate topology simplification, A class of algorithms which require nonlinear time to maintain disjoint sets, A simplified construction of nonlinear Davenport-Schinzel sequences, Proof of a conjecture of Erdős and Turán, Fast congruence closure and extensions, A linear systolic algorithm for the connected component problem, Worst-case analysis of the set-union problem with extended backtracking, On the relationship of congruence closure and unification, On the row merge tree for sparse LU factorization with partial pivoting, An efficient abstract machine for safe ambients, Lexicographic permutations with restrictions, Learning deterministic even linear languages from positive examples, Finding dominators via disjoint set union, Linear time analysis of properties of conflict-free and general Petri nets, A simple and efficient union-find-delete algorithm, An efficient PQ-graph algorithm for solving the graph-realization problem, Ranking arborescences in O(Km log n) time, Mixed hypergraphs with bounded degree: Edge-coloring of mixed multigraphs., Finding the most vital node of a shortest path., Dynamic orthogonal range queries in OLAP., An \(O(EV\log^2V)\) algorithm for the maximal flow problem, 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, An algorithm for testing lossless join property in relational databases, Pathlistings applied to data flow analysis, Max-coloring paths: tight bounds and extensions, A state-of-the-art review of parallel-machine scheduling research, The saga of minimum spanning trees, Finding connected components of an intersection graph of squares in the Euclidean plane, A note on data structures for maintaining bipartitions, An O\((n\log n)\) version of the Averbakh-Berman algorithm for the robust median of a tree, Unifications, deunifications, and their complexity, Practical and efficient circle graph recognition, Practical and efficient split decomposition via graph-labelled trees, Extending common intervals searching from permutations to sequences, Fast sequential importance sampling to estimate the graph reliability polynomial, Using bisimulation proof techniques for the analysis of distributed abstract machines, Finding the most vital edge with respect to minimum spanning tree in weighted graphs, Verifying the correctness and amortized complexity of a union-find implementation in separation logic with time credits, Maintaining bridge-connected and biconnected components on-line, A 0.5358-approximation for Bandpass-2, Two linear time Union--Find strategies for image processing, Undirected \(s\)--\(t\) connectivity in polynomial time and sublinear space, Shortcutting directed and undirected networks with a degree constraint, New constructions for provably-secure time-bound hierarchical key assignment schemes, Maintenance of 2- and 3-edge-connected components of graphs. I, Another variation on the common subexpression problem, Generalized Davenport-Schinzel sequences with linear upper bound, \(P_ 4\)-trees and substitution decomposition, A linear algorithm for MLL proof net correctness and sequentialization, An optimal algorithm for the period of a strongly connected digraph, Randomized range-maxima in nearly-constant parallel time, Simple and optimal output-sensitive construction of contour trees using monotone paths, Edge-disjoint spanning trees and depth-first search, Testing flow graph reducibility, Linear expected time of a simple union-find algorithm, Fast reoptimization for the minimum spanning tree problem, Linear unification, Finding an anti-risk path between two nodes in undirected graphs, Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree, Finding a feasible flow in a strongly connected network, Space-time trade off in implementing certain set operations, High girth augmented trees are huge, A new data structure for the UNION-FIND problem, A fast algorithm for constructing a tree automaton recognizing a congruential tree language, A fast algorithm for finding interlocking sets, A note on set union with arbitrary deunions, A practical unification algorithm, Efficient Union-Find for planar graphs and other sparse graph classes, Salembier's min-tree algorithm turned into breadth first search, Combination of convex theories: modularity, deduction completeness, and explanation, Extremal problems for colored trees and Davenport-Schinzel sequences, On-line computation of transitive closures of graphs, A linear-time algorithm for a special case of disjoint set union, The set union problem with dynamic weighted backtracking, On constructing the elimination tree, A polynomial time algorithm for finding the prime factors of Cartesian- product graphs, A faster computation of the most vital edge of a shortest path, Testing string superprimitivity in parallel, A theory of alternating paths and blossoms for proving correctness of the \(O(\sqrt{V}E)\) general graph maximum matching algorithm, Fast algorithms for the undirected negative cost cycle detection problem
