NDLI: Union-find with deletions

Please wait, while we are loading the content...

Static optimality and dynamic search-optimality in lists and trees

Optimal time-space trade-offs for non-comparison-based sorting

Union-find with deletions

A locality-preserving cache-oblivious dynamic dictionary

Cache oblivious search trees via binary trees of small height

An approximation algorithm for the group Steiner problem

On directed Steiner trees

An 8/13-approximation algorithm for the asymmetric maximum TSP

Approximability of dense and sparse instances of minimum 2-connectivity, TSP and path problems

An ear decomposition approach to approximating the smallest 3-edge connected spanning subgraph of a multigraph

Censorship resistant peer-to-peer content addressable networks

Web caching with request reordering

Improved algorithms for the data placement problem

Undiscretized dynamic programming: faster algorithms for facility location and related problems on trees

Temporary tasks assignment resolved

Dense point sets have sparse Delaunay triangulations: or "…but not too nasty"

Delaunay triangulation programs on surface data

Quality meshing with weighted Delaunay refinement

Linear-size approximate voronoi diagrams

Motorcycle graphs and straight skeletons

Faster approximation schemes for fractional multicommodity flow problems

Flows over time with load-dependent transit times

Improved bounds for the unsplittable flow problem

NP-hardness of broadcast scheduling and inapproximability of single-source unsplittable min-cost flow

How unfair is optimal routing?

Approximation algorithms for grammar-based compression

Improving table compression with combinatorial optimization

Linear-time compression of bounded-genus graphs into information-theoretically optimal number of bits

Succinct representations of lcp information and improvements in the compressed suffix arrays

Succinct indexable dictionaries with applications to encoding k-ary trees and multisets

Guessing secrets with inner product questions

Guessing secrets efficiently via list decoding

How to cut a cake almost fairly

The mathematics of playing golf

Computing shortest paths with comparisons and additions

An optimal algorithm for checking regularity: (extended abstract)

Edge dominating and hypomatchable sets

An algorithm for counting maximum weighted independent sets and its applications

Algorithms for quantified Boolean formulas

Balls and bins models with feedback

A note on random 2-SAT with prescribed literal degrees

Mixing time and long paths in graphs

The diameter of a long range percolation graph

Is the internet fractal?

Center and diameter problems in plane triangulations and quadrangulations

Symmetric drawings of triconnected planar graphs

Layout area of the hypercube: (extended abstract)

I/O-optimal algorithms for planar graphs using separators

Polynomial time recognition of P4-structure

Adaptive intersection and t-threshold problems

Separable attributes: a technique for solving the sub matrices character count problem

Tiling groups for Wang tiles

Generating random factored numbers, easily

Tight bounds for worst-case equilibria

Broadcast scheduling: when fairness is fine

Harmonic broadcasting is optimal

Windows scheduling problems for broadcast systems

Scheduling protocols for switches with large envelopes

Covering shapes by ellipses

Slice and dice: a simple, improved approximate tiling recipe

Binary space partitions for line segments with a limited number of directions

Closest-point problems simplified on the RAM

Semi-online maintenance of geometric optima and measures

Generalized clustering

New bounds for multi-dimensional packing

Computer assisted proof of optimal approximability results

MAX CUT in cubic graphs

Approximating minimum unsatisfiability of linear equations

On-line algorithms for the dynamic traveling repair problem

Competitive on-line switching policies

A randomized online algorithm for bandwidth utilization

Caching with expiration times

On-line scheduling of a single machine to minimize total weighted completion time

Hardware-assisted computation of depth contours

The freeze-tag problem: how to wake up a swarm of robots

The wake up and report problem is time-equivalent to the firing squad synchronization problem

Tree exploration with little memory

Efficient proper 2-coloring of almost disjoint hypergraphs

Experimental analysis of simple, distributed vertex coloring algorithms

On semidefinite programming relaxations for graph coloring and vertex cover

Approximating k-cuts via network strength

Reductions in streaming algorithms, with an application to counting triangles in graphs

Sampling from a moving window over streaming data

Maintaining stream statistics over sliding windows: (extended abstract)

Testing satisfiability

Efficient pattern-matching with don't cares

Efficient algorithms for document retrieval problems

The string edit distance matching problem with moves

Simple approximation algorithm for nonoverlapping local alignments

A sub-quadratic sequence alignment algorithm for unrestricted cost matrices

On adaptive deterministic gossiping in ad hoc radio networks

Expansion of product replacement graphs

Explicit constructions of selectors and related combinatorial structures, with applications

Derandomized dimensionality reduction with applications

Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms

Existence theorems, lower bounds and algorithms for scheduling to meet two objectives

Scheduling split intervals

Throughput maximization of real-time scheduling with batching

(Incremental) priority algorithms

Improved algorithms for stretch scheduling

Shape dimension and approximation from samples

Smooth-surface reconstruction in near-linear time

Computing the writhing number of a polygonal knot

Pseudo-line arrangements: duality, algorithms, and applications

On the overlay of envelopes in four dimensions

Preprocessing an undirected planar network to enable fast approximate distance queries

Approximate distance oracles for geometric graphs

Oracles for distances avoiding a link-failure

Roundtrip spanners and roundtrip routing in directed graphs

Light spanners and approximate TSP in weighted graphs with forbidden minors

Capacitated vertex covering with applications

Construction of probe interval models

A new algorithm for protein folding in the HP model

An optimal (expected time) algorithm for minimizing lab costs in DNA sequencing

Approximating minimum quartet inconsistency: (abstract)

Matrix rounding under the Lp-discrepancy measure and its application to digital halftoning

Smoothed analysis of the perceptron algorithm for linear programming

A fully combinatorial algorithm for submodular function minimization

0/1 optimization and 0/1 primal separation are equivalent

Labeling schemes for flow and connectivity

Reachability and distance queries via 2-hop labels

Improved labeling scheme for ancestor queries

A comparison of labeling schemes for ancestor queries

Incentive-compatible online auctions for digital goods

Online algorithms for market clearing

Pricing multicasting in more practical network models

Frugal path mechanisms

an approximation algorithm for minimum-cost vertex-connectivity problems

Union-find with deletions

Content Provider	ACM Digital Library
Author	Kaplan, Haim Tarjan, Robert E. Shafrir, Nira
Abstract	In the classical union-find problem we maintain a partition of a universe of n elements into disjoint sets subject to the operations union and find. The operation union(A, B, C) replaces sets A and B in the partition by their union, given the name C. The operation find(x) returns the name of the set containing the element x. In this paper we revisit the union-find problem in a context where the underlying partitioned universe is not fixed. Specifically, we allow a delete(x) operation which removes the element x from the set containing it. We consider both worst-case performance and amortized performance. In both settings the challenge is to dynamically keep the size of the structure representing each set proportional to the number of elements in the set which may now decrease as a result of deletions.For any fixed k, we describe a data structure that supports find and delete in O(logkn) worst-case time and union in O(k) worst-case time. This matches the best possible worst-case bounds for find and union in the classical setting. Furthermore, using an incremental global rebuilding technique we obtain a reduction converting any union-find data structure to a union-find with deletions data structure. Our reduction is such that the time bounds for find and union change only by a constant factor. The time it takes to delete an element x is the same as the time it takes to find the set containing x plus the time it takes to unite a singleton set with this set.In an amortized setting a classical data structure of Tarjan supports a sequence of m finds and at most n unions on a universe of n elements in O(n + mα(m + n, n, log n)) time where α(m, n, l) = min{k \| Ak(⌊m/n⌋) > l} and Ai(j) is Ackermann's function as described in [6]. We refine the analysis of this data structure and show that in fact the cost of each find is proportional to the size of the corresponding set. Specifically, we show that one can pay for a sequence of union and find operations by charging a constant to each participating element and O(α(m, n, log(l))) for a find of an element in a set of size l. We also show how keep these amortized costs for each find and each participating element while allowing deletions. The amortized cost of deleting an element from a set of l elements is the same as the amortized cost of finding the element; namely, O(α(m, n, log(l))).
Starting Page	19
Ending Page	28
Page Count	10
File Format	PDF
ISBN	089871513X
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-01-06
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in