Efficiency of a Good But Not Linear Set Union Algorithm

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Efficiency of a Good But Not Linear Set Union Algorithm

Full text

Pdf (665 KB)

Source

Journal of the ACM (JACM) archive
Volume 22 , Issue 2 (April 1975) table of contents

Pages: 215 - 225

Year of Publication: 1975

ISSN:0004-5411

Author

Robert Endre Tarjan

Department of Electrical Engineering and Computer Sciences, Computer Science Division, University of California, Berkeley, CA

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 36, Downloads (12 Months): 275, Citation Count: 159

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321879.321884 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	kCKERMANN, W Zum Hllbertshen Aufbau der reelen Zahlen Math. Ann. 99 (1928), 118-133.
	2	A. V. Aho , J. E. Hopcroft , J. D. Ullman, On finding lowest common ancestors in trees, Proceedings of the fifth annual ACM symposium on Theory of computing, p.253-265, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804056]
	3	Bruce W. Arden , Bernard A. Galler , Robert M. Graham, An algorithm for equivalence declarations, Communications of the ACM, v.4 n.7, p.310-314, July 1961 [doi>10.1145/366622.366626]
	4	Vaclav Chvatal , David A. Klarner , Donald E. Knuth, Selected combinatorial research problems., Stanford University, Stanford, CA, 1972
	5	FISCHER, M J, Efficiency of eqmvalence algorithms. In Complexity of Computer Computations, R. E, Miller and J W Thatcher, Eds., Plenum Press, New York, 1972, pp. 153-168.
	6	Benrard A. Galler , Michael J. Fisher, An improved equivalence algorithm, Communications of the ACM, v.7 n.5, p.301-303, May 1964 [doi>10.1145/364099.364331]
	7	HOPCROFT, J , AND ULLMAN, J.D. Set-mergmg algorithms. SIAM J. Comput ~ (Dec. 1973), 294-303.
	8	HOPCROFT, J Private communication.
	9	A. Kershenbaum , R. Van Slyke, Computing minimum spanning trees efficiently, Proceedings of the ACM annual conference, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800193.569966]
	10	Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
	11	PATERSON, M. Unpublished report, U. of Warwick, Coventry, Great Britain.
	12	STEARNS, R E., AND ROSENKRANTZ, D. J. Table machine simulation. 1Oth Annum SWAT Conf. Proc, 1969, pp 118-128.
	13	Robert Tarjan, Testing flow graph reducibility, Proceedings of the fifth annual ACM symposium on Theory of computing, p.96-107, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804040]
	14	TARJAN, R. Finding dominators in directed graphs SIAM J Comput. S (March 1974), 62-89.

CITED BY 159

	Harold N. Gabow , Robert Endre Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.246-251, December 1983
	Donald B. Johnson , Samuel D. Kashdan, Lower Bounds for Selection in X + Y and Other Multisets, Journal of the ACM (JACM), v.25 n.4, p.556-570, Oct. 1978
	Haim Kaplan , Ron Shamir , Robert E. Tarjan, Faster and simpler algorithm for sorting signed permutations by reversals, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.344-351, January 05-07, 1997, New Orleans, Louisiana, United States
	John H. Reif , Harry R. Lewis, Symbolic evaluation and the global value graph, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.104-118, January 17-19, 1977, Los Angeles, California
	Ajit Agrawal , Philip Klein , R. Ravi, When trees collide: an approximation algorithm for the generalized Steiner problem on networks, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.134-144, May 05-08, 1991, New Orleans, Louisiana, United States
	M. S. Chang , C. Y. Tang , R. C. T. Lee, A unified approach for solving bottleneck k-bipartition problems, Proceedings of the 19th annual conference on Computer Science, p.39-47, April 1991, San Antonio, Texas, United States
	Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Meldable heaps and boolean union-find, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	P. Flajolet , J. Françon , J. Vuillemin, Computing integrated costs of sequences of operations with application to dictionaries, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.49-61, April 30-May 02, 1979, Atlanta, Georgia, United States
	J. A. La Poutré, New techniques for the union-find problem, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.54-63, January 22-24, 1990, San Francisco, California, United States
	Greg Nelson , Derek C. Oppen, Fast Decision Procedures Based on Congruence Closure, Journal of the ACM (JACM), v.27 n.2, p.356-364, April 1980
	M. Fredman , M. Saks, The cell probe complexity of dynamic data structures, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.345-354, May 14-17, 1989, Seattle, Washington, United States
	Joseph W. Liu, A compact row storage scheme for Cholesky factors using elimination trees, ACM Transactions on Mathematical Software (TOMS), v.12 n.2, p.127-148, June 1986
	Robert E. Shostak, Deciding Combinations of Theories, Journal of the ACM (JACM), v.31 n.1, p.1-12, Jan. 1984
	Robert B. Jones , David L. Dill , Jerry R. Burch, Efficient validity checking for processor verification, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.2-6, November 05-09, 1995, San Jose, California, United States
	Andrew V. Goldberg , Alexander V. Karzanov, Path problems in skew-symmetric graphs, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.526-535, January 23-25, 1994, Arlington, Virginia, United States
	Kenneth L. Clarkson, Fast expected-time and approximation algorithms for geometric minimum spanning trees, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.342-348, December 1984
	Hussein M. Alnuweiri , Viktor K. Prasanna, Parallel Architectures and Algorithms for Image Component Labeling, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.10, p.1014-1034, October 1992
	Hanan Samet, The Quadtree and Related Hierarchical Data Structures, ACM Computing Surveys (CSUR), v.16 n.2, p.187-260, June 1984
	J. W. Jaromczyk , M. Kowaluk, A note on relative neighborhood graphs, Proceedings of the third annual symposium on Computational geometry, p.233-241, June 08-10, 1987, Waterloo, Ontario, Canada
	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979
	Mikkel Thorup, Near-optimal fully-dynamic graph connectivity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.343-350, May 21-23, 2000, Portland, Oregon, United States
	Susan L. Graham , Mark Wegman, A Fast and Usually Linear Algorithm for Global Flow Analysis, Journal of the ACM (JACM), v.23 n.1, p.172-202, Jan. 1976
	B. Chazelle , B. Rosenberg, Computing partial sums in multidimensional arrays, Proceedings of the fifth annual symposium on Computational geometry, p.131-139, June 05-07, 1989, Saarbruchen, West Germany
	Peter J. Downey , Ravi Sethi , Robert Endre Tarjan, Variations on the Common Subexpression Problem, Journal of the ACM (JACM), v.27 n.4, p.758-771, Oct. 1980
	Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.114-122, May 11-13, 1981, Milwaukee, Wisconsin, United States
	Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, An Automatic Technique for Selection of Data Representations in SETL Programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.126-143, April 1981
	Richard J. Anderson, Primitives for asynchronous list compression, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.199-208, June 29-July 01, 1992, San Diego, California, United States
	Ronald L. Rivest , Robert E. Schapire, Diversity-based inference of finite automata, Journal of the ACM (JACM), v.41 n.3, p.555-589, May 1994
	Richard J. Lipton , Robert Sedgewick , Jacobo Valdes, Programming aspects of VLSI: (preliminary version), Proceedings of the 9th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.57-65, January 25-27, 1982, Albuquerque, Mexico
	Louis Ibarra, Fully dynamic algorithms for chordal graphs, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.923-924, January 17-19, 1999, Baltimore, Maryland, United States
	Dana Angluin, Inference of Reversible Languages, Journal of the ACM (JACM), v.29 n.3, p.741-765, July 1982
	Martin Loebl , Jaroslav Nešetřil, Linearity and unprovability of set union problem, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.360-366, May 02-04, 1988, Chicago, Illinois, United States
	B Bollobás , I Simon, On the expected behavior of disjoint set union algorithms, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.224-231, May 06-08, 1985, Providence, Rhode Island, United States
	Harold N. Gabow, An Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs, Journal of the ACM (JACM), v.23 n.2, p.221-234, April 1976
	Zvi Galil , Christoph M. Hoffmann , Eugene M. Luks , Claus P. Schnorr , Andreas Weber, An O(n3log n) deterministic and an O(n3) Las Vegs isomorphism test for trivalent graphs, Journal of the ACM (JACM), v.34 n.3, p.513-531, July 1987
	Mingdong Feng , Charles E. Leiserson, Efficient detection of determinacy races in Cilk programs, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.1-11, June 23-25, 1997, Newport, Rhode Island, United States
	John H. Reif, Symbolic program analysis in almost linear time, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.76-83, January 23-25, 1978, Tucson, Arizona
	Michel X. Goemans , David P. Williamson, A general approximation technique for constrained forest problems, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.307-316, September 1992, Orlando, Florida, United States
	Robert E. Shostak, An algorithm for reasoning about equality, Communications of the ACM, v.21 n.7, p.583-585, July 1978
	Krishna Palem , Barbara Simons, Scheduling time-critical instructions on RISC machines, Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.270-280, December 1989, San Francisco, California, United States
	Andrew C. Yao, Space-time tradeoff for answering range queries (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.128-136, May 05-07, 1982, San Francisco, California, United States
	Bernard Chazelle, A minimum spanning tree algorithm with inverse-Ackermann type complexity, Journal of the ACM (JACM), v.47 n.6, p.1028-1047, Nov. 2000
	Andrew Chi-chih Yao, On the average behavior of set merging algorithms (Extended Abstract), Proceedings of the eighth annual ACM symposium on Theory of computing, p.192-195, May 03-05, 1976, Hershey, Pennsylvania, United States
	Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States
	Bryant A. Julstrom, Encoding rectilinear Steiner trees as lists of edges, Proceedings of the 2001 ACM symposium on Applied computing, p.356-360, March 2001, Las Vegas, Nevada, United States
	David Lee , Mihalis Yannakakis, Closed Partition Lattice and Machine Decomposition, IEEE Transactions on Computers, v.51 n.2, p.216-228, February 2002
	J. A. La Poutré, Lower bounds for the union-find and the split-find problem on pointer machines, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.34-44, May 13-17, 1990, Baltimore, Maryland, United States
	Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.918-926, January 09-11, 2000, San Francisco, California, United States
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001
	Ferenc Rákóczi, Fast recognition of the nilpotency of permutation groups, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.265-269, July 10-12, 1995, Montreal, Quebec, Canada
	Harold N. Gabow, An Almost-Linear Algorithm for Two-Processor Scheduling, Journal of the ACM (JACM), v.29 n.3, p.766-780, July 1982
	Ronald I. Greenberg, Finding connected components on a scan line array processor, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.195-202, June 24-26, 1995, Santa Barbara, California, United States
	Allen Leung , Krishna V. Palem , Amir Pnueli, Scheduling time-constrained instructions on pipelined processors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.73-103, Jan. 2001
	Ron Cytron , Reid Gershbein, Efficient accommodation of may-alias information in SSA form, ACM SIGPLAN Notices, v.28 n.6, p.36-45, June 1993
	Robert Endre Tarjan, Reference machines require non-linear time to maintain disjoint sets, Proceedings of the ninth annual ACM symposium on Theory of computing, p.18-29, May 04-04, 1977, Boulder, Colorado, United States
	Patrick A. V. Hall , Geoff R. Dowling, Approximate String Matching, ACM Computing Surveys (CSUR), v.12 n.4, p.381-402, Dec. 1980
	Richard M. Karp , Robert Endre Tarjan, Linear expected-time algorithms for connectivity problems (Extended Abstract), Proceedings of the twelfth annual ACM symposium on Theory of computing, p.368-377, April 28-30, 1980, Los Angeles, California, United States
	Chung Keung Poon, Dynamic orthogonal range queries in OLAP, Theoretical Computer Science, v.296 n.3, p.487-510, 14 March 2003
	Renato Werneck , João Setubal , Arlindo da Conceicão, Finding minimum congestion spanning trees, Journal of Experimental Algorithmics (JEA), 5, p.11-es, 2000
	W. J. Hsu, New algorithms for comparing symbol sequences, Proceedings of the 1987 Fall Joint Computer Conference on Exploring technology: today and tomorrow, p.381-389, December 1987, Dallas, Texas, United States
	I. S. Duff , J. K. Reid, An Implementation of Tarjan's Algorithm for the Block Triangularization of a Matrix, ACM Transactions on Mathematical Software (TOMS), v.4 n.2, p.137-147, June 1978
	Krishna V. Palem , Barbara B. Simons, Scheduling time-critical instructions on RISC machines, ACM Transactions on Programming Languages and Systems (TOPLAS), v.15 n.4, p.632-658, Sept. 1993
	C. Elkan, A decision procedure for conjunctive query disjointness, Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-139, March 1989, Philadelphia, Pennsylvania, United States
	Greg Barnes , Walter L. Ruzzo, Deterministic algorithms for undirected s-t connectivity using polynomial time and sublinear space., Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.43-53, May 05-08, 1991, New Orleans, Louisiana, United States
	Danny Dolev , Cynthia Dwork , Nicholas Pippenger , Avi Wigderson, Superconcentrators, generalizers and generalized connectors with limited depth, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.42-51, December 1983
	Marc J. van Kreveld , Mark H. Overmars, Union-copy structures and dynamic segment trees, Journal of the ACM (JACM), v.40 n.3, p.635-652, July 1993
	D Harel, A linear algorithm for finding dominators in flow graphs and related problems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.185-194, May 06-08, 1985, Providence, Rhode Island, United States
	Robert E. Tarjan , Jan van Leeuwen, Worst-case Analysis of Set Union Algorithms, Journal of the ACM (JACM), v.31 n.2, p.245-281, April 1984
	Zvi Galil , Amnon Naamad, Network flow and generalized path compression, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.13-26, April 30-May 02, 1979, Atlanta, Georgia, United States
	Markku Tamminen , Hanan Samet, Efficient octree conversion by connectivity labeling, ACM SIGGRAPH Computer Graphics, v.18 n.3, p.43-51, July 1984
	Yossi Shiloach , Shimon Even, An On-Line Edge-Deletion Problem, Journal of the ACM (JACM), v.28 n.1, p.1-4, Jan. 1981
	Alain Deutsch, On the complexity of escape analysis, Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.358-371, January 15-17, 1997, Paris, France
	Zvi Galil, Efficient algorithms for finding maximum matching in graphs, ACM Computing Surveys (CSUR), v.18 n.1, p.23-38, March 1986
	Mikkel Thorup, Decremental dynamic connectivity, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.305-313, January 05-07, 1997, New Orleans, Louisiana, United States
	Daniel G. Bobrow, Managing Reentrant Structures Using Reference Counts, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.3, p.269-273, July 1980
	Stephen Alstrup , Amir M. Ben-Amram , Theis Rauhe, Worst-case and amortised optimality in union-find (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.499-506, May 01-04, 1999, Atlanta, Georgia, United States
	Ulrich Finkler , Kurt Mehlhorn, Checking priority queues, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.901-902, January 17-19, 1999, Baltimore, Maryland, United States
	Andrew V. Goldberg , Satish Rao, Beyond the flow decomposition barrier, Journal of the ACM (JACM), v.45 n.5, p.783-797, Sept. 1998
	Yuanlin Zhang , Roland H. C. Yap, Incrementally solving functional constraints, Eighteenth national conference on Artificial intelligence, p.973-974, July 28-August 01, 2002, Edmonton, Alberta, Canada
	A. Meijster , M. H. F. Wilkinson, A Comparison of Algorithms for Connected Set Openings and Closings, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.24 n.4, p.484-494, April 2002
	Peter Downey , Hanan Samet , Ravi Sethi, Off-line and on-line algorithms for deducing equalities, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.158-170, January 23-25, 1978, Tucson, Arizona
	James F. Allen , Alan M. Frisch, What's in a semantic network?, Proceedings of the 20th annual meeting on Association for Computational Linguistics, June 16-18, 1982, Toronto, Ontario, Canada
	F. Cazals , F. Chazal , T. Lewiner, Molecular shape analysis based upon the morse-smale complex and the connolly function, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Edmond Schonberg , Jacob T. Schwartz , Micha Sharir, Automatic data structure selection in SETL, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.197-210, January 29-31, 1979, San Antonio, Texas
	Kenji Suzuki , Isao Horiba , Noboru Sugie, Linear-time connected-component labeling based on sequential local operations, Computer Vision and Image Understanding, v.89 n.1, p.1-23, January 2003
	Christos D. Zaroliagis, Implementations and experimental studies of dynamic graph algorithms, Experimental algorithmics: from algorithm design to robust and efficient software, Springer-Verlag New York, Inc., New York, NY, 2002
	Wim H. Hesselink, Salembier's Min-tree algorithm turned into breadth first search, Information Processing Letters, v.88 n.5, p.225-229, 16 December 2003
	Fu Chang , Chun-Jen Chen , Chi-Jen Lu, A linear-time component-labeling algorithm using contour tracing technique, Computer Vision and Image Understanding, v.93 n.2, p.206-220, February 2004
	Ran Mendelson , Mikkel Thorup , Uri Zwick, Meldable RAM priority queues and minimum directed spanning trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Michael A. Bender , Saurabh Sethia , Steven S. Skiena, Data structures for maintaining set partitions, Random Structures & Algorithms, v.25 n.1, p.43-67, August 2004
	M. S. Paterson , M. N. Wegman, Linear unification, Proceedings of the eighth annual ACM symposium on Theory of computing, p.181-186, May 03-05, 1976, Hershey, Pennsylvania, United States
	Glenn Ammons , Rastislav Bodík , James R. Larus, Mining specifications, ACM SIGPLAN Notices, v.37 n.1, p.4-16, Jan. 2002
	Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM (JACM), v.48 n.4, p.723-760, July 2001
	Michael B. Dillencourt , Hannan Samet , Markku Tamminen, A general approach to connected-component labeling for arbitrary image representations, Journal of the ACM (JACM), v.39 n.2, p.253-280, April 1992
	Zvi Galil , Giuseppe F. Italiano, Data structures and algorithms for disjoint set union problems, ACM Computing Surveys (CSUR), v.23 n.3, p.319-344, Sept. 1991
	Daniel Dominic Sleator , Robert Endre Tarjan, Self-adjusting binary search trees, Journal of the ACM (JACM), v.32 n.3, p.652-686, July 1985
	Mikkel Thorup, Undirected single-source shortest paths with positive integer weights in linear time, Journal of the ACM (JACM), v.46 n.3, p.362-394, May 1999
	Enrico Nardelli , Guido Proietti , Peter Widmayer, Finding the most vital node of a shortest path, Theoretical Computer Science, v.296 n.1, p.167-177, 4 March 2003
	Greg DeFouw , David Grove , Craig Chambers, Fast interprocedural class analysis, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.222-236, January 19-21, 1998, San Diego, California, United States
	K. P. Belkhale , P. Banerjee, Parallel Algorithms for Geometric Connected Component Labeling on a Hypercube Multiprocessor, IEEE Transactions on Computers, v.41 n.6, p.699-709, June 1992
	Liam Roditty , Uri Zwick, A fully dynamic reachability algorithm for directed graphs with an almost linear update time, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	David Grove , Craig Chambers, A framework for call graph construction algorithms, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.6, p.685-746, November 2001
	Naoki Kobayashi, Type-Based Useless-Variable Elimination, Higher-Order and Symbolic Computation, v.14 n.2-3, p.221-260, September 2001
	A. Unnikrishnan , P. Shankar , Y. V. Venkatesh, Threaded Linear Hierarchical Quadtrees for Computation of Geometric Properties of Binary Images, IEEE Transactions on Software Engineering, v.14 n.5, p.659-665, May 1988
	Thomas Lewiner , Helio Lopes , Geovan Tavares, Applications of Forman's Discrete Morse Theory to Topology Visualization and Mesh Compression, IEEE Transactions on Visualization and Computer Graphics, v.10 n.5, p.499-508, September 2004
	Bryant A. Julstrom, The blob code is competitive with edge-sets in genetic algorithms for the minimum routing cost spanning tree problem, Proceedings of the 2005 conference on Genetic and evolutionary computation, June 25-29, 2005, Washington DC, USA
	Mikkel Thorup, Worst-case update times for fully-dynamic all-pairs shortest paths, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Hanan Samet , Markku Tamminen, Efficient Component Labeling of Images of Arbitrary Dimension Represented by Linear Bintrees, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.10 n.4, p.579-586, July 1988
	Drago Krznaric , Christos Levcopoulos, Computing a threaded quadtree from the Delaunay triangulation in linear time, Nordic Journal of Computing, v.5 n.1, p.1-18, Spring 1998
	Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Computational Geometry: Theory and Applications, v.24 n.2, p.75-94, February 2003
	Yi-Jen Chiang , Tobias Lenz , Xiang Lu , Günter Rote, Simple and optimal output-sensitive construction of contour trees using monotone paths, Computational Geometry: Theory and Applications, v.30 n.2, p.165-195, February 2005
	David Detlefs , Greg Nelson , James B. Saxe, Simplify: a theorem prover for program checking, Journal of the ACM (JACM), v.52 n.3, p.365-473, May 2005
	Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Charles E. Leiserson, On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain
	Henning Makholm , J. B. Wells, Type inference, principal typings, and let-polymorphism for first-class mixin modules, ACM SIGPLAN Notices, v.40 n.9, September 2005
	Daniel Král' , Jan Kratochvíl , Heinz-Jürgen Voss, Mixed hypergraphs with bounded degree: edge-coloring of mixed multigraphs, Theoretical Computer Science, v.295 n.1-3, p.263-278, 24 February 2003
	T-H. Hubert Chan , Anupam Gupta, Small hop-diameter sparse spanners for doubling metrics, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.70-78, January 22-26, 2006, Miami, Florida
	Venkatesh Choppella , Christopher T. Haynes, Source-tracking unification, Information and Computation, v.201 n.2, p.121-159, September 15, 2005
	Guido Proietti , Peter Widmayer, A truthful mechanism for the non-utilitarian minimum radius spanning tree problem, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Susan L. Graham , Mark Wegman, A fast and usually linear algorithm for global flow analysis, Proceedings of the 2nd ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-34, January 20-22, 1975, Palo Alto, California
	Haim Kaplan , Nira Shafrir , Robert E. Tarjan, Union-find with deletions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.19-28, January 06-08, 2002, San Francisco, California
	Damien Pous, Using bisimulation proof techniques for the analysis of distributed abstract machines, Theoretical Computer Science, v.402 n.2-3, p.199-220, August, 2008
	Andrew Gilpin , Tuomas Sandholm, Lossless abstraction of imperfect information games, Journal of the ACM (JACM), v.54 n.5, p.25-es, October 2007
	H. Fernau, Identifying Terminal Distinguishable Languages, Annals of Mathematics and Artificial Intelligence, v.40 n.3-4, p.263-281, March 2004
	Greg N. Frederickson , Roberto Solis-Oba, Increasing the weight of minimum spanning trees, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.539-546, January 28-30, 1996, Atlanta, Georgia, United States
	Stephen Alstrup , Jens Peter Secher , Mikkel Thorup, Word encoding tree connectivity works, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.498-499, January 09-11, 2000, San Francisco, California, United States
	Toshihide Ibaraki , Hussein M. Abdel-Wahab , Tiko Kameda, Design of Minimum-Cost Deadlock-Free Systems, Journal of the ACM (JACM), v.30 n.4, p.736-751, Oct. 1983
	Melissa E. O'Neill , F. Warren Burton, Smarter garbage collection with simplifiers, Proceedings of the 2006 workshop on Memory system performance and correctness, October 22-22, 2006, San Jose, California
	R. Marfil , L. Molina-Tanco , A. Bandera , J. A. Rodríguez , F. Sandoval, Pyramid segmentation algorithms revisited, Pattern Recognition, v.39 n.8, p.1430-1451, August, 2006
	Rajneesh Hegde, Finding 3-shredders efficiently, ACM Transactions on Algorithms (TALG), v.2 n.1, p.14-43, January 2006
	Susan Elias , K. S. Easwarakumar , Richard Chbeir, Dynamic consistency checking for temporal and spatial relations in multimedia presentations, Proceedings of the 2006 ACM symposium on Applied computing, April 23-27, 2006, Dijon, France
	Andrew Gilpin , Tuomas Sandholm, Finding equilibria in large sequential games of imperfect information, Proceedings of the 7th ACM conference on Electronic commerce, p.160-169, June 11-15, 2006, Ann Arbor, Michigan, USA
	Pankaj K. Agarwal , Lars Arge , Ke Yi, I/O-efficient batched union-find and its applications to terrain analysis, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA
	Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, New constructions for provably-secure time-bound hierarchical key assignment schemes, Proceedings of the 12th ACM symposium on Access control models and technologies, June 20-22, 2007, Sophia Antipolis, France
	Ran Mendelson , Robert E. Tarjan , Mikkel Thorup , Uri Zwick, Melding priority queues, ACM Transactions on Algorithms (TALG), v.2 n.4, p.535-556, October 2006
	J. Martín-Herrero, Hybrid object labelling in digital images, Machine Vision and Applications, v.18 n.1, p.1-15, January 2007
	Robert Nieuwenhuis , Albert Oliveras, Fast congruence closure and extensions, Information and Computation, v.205 n.4, p.557-580, April, 2007
	Gruia Calinescu, A note on data structures for maintaining bipartitions, Journal of Discrete Algorithms, v.5 n.1, p.129-134, March, 2007
	Y. André , A. C. Caron , D. Debarbieux , Y. Roos , S. Tison, Path constraints in semistructured data, Theoretical Computer Science, v.385 n.1-3, p.11-33, October, 2007
	Aleksej Di Salvo , Guido Proietti, Swapping a failing edge of a shortest paths tree by minimizing the average stretch factor, Theoretical Computer Science, v.383 n.1, p.23-33, September, 2007
	Mikkel Thorup, Equivalence between priority queues and sorting, Journal of the ACM (JACM), v.54 n.6, p.28-es, December 2007
	Erik D. Demaine , John Iacono , Stefan Langerman, Retroactive data structures, ACM Transactions on Algorithms (TALG), v.3 n.2, p.13-es, May 2007
	Chris Lattner , Andrew Lenharth , Vikram Adve, Making context-sensitive points-to analysis with heap cloning practical for the real world, ACM SIGPLAN Notices, v.42 n.6, June 2007
	Michael Emmi , Rupak Majumdar , Koushik Sen, Dynamic test input generation for database applications, Proceedings of the 2007 international symposium on Software testing and analysis, July 09-12, 2007, London, United Kingdom
	Guillaume Damiand, Topological model for 3D image representation: Definition and incremental extraction algorithm, Computer Vision and Image Understanding, v.109 n.3, p.260-289, March, 2008
	Christophe Guillon , Fabrice Rastello , Thierry Bidault , Florent Bouchez, Procedure placement using temporal-ordering information: Dealing with code size expansion, Journal of Embedded Computing, v.1 n.4, p.437-459, December 2005
	Michael D. Adams , R. Kent Dybvig, Efficient nondestructive equality checking for trees and graphs, ACM SIGPLAN Notices, v.43 n.9, September 2008
	Lifeng He , Yuyan Chao , Kenji Suzuki , Kesheng Wu, Fast connected-component labeling, Pattern Recognition, v.42 n.9, p.1977-1987, September, 2009
	Zoran Budimlić , Mackale Joyner , Ken Kennedy, Improving Compilation of Java Scientific Applications, International Journal of High Performance Computing Applications, v.21 n.3, p.251-265, August 2007
	Seth Pettie, Splay trees, Davenport-Schinzel sequences, and the deque conjecture, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1115-1124, January 20-22, 2008, San Francisco, California
	Sylvain Conchon , Jean-Christophe Filliâtre, A persistent union-find data structure, Proceedings of the 2007 workshop on Workshop on ML, October 05-05, 2007, Freiburg, Germany
	Alfredo De Santis , Anna Lisa Ferrara , Barbara Masucci, New constructions for provably-secure time-bound hierarchical key assignment schemes, Theoretical Computer Science, v.407 n.1-3, p.213-230, November, 2008
	Changjun Wu , Ananth Kalyanaraman, An efficient parallel approach for identifying protein families in large-scale metagenomic data sets, Proceedings of the 2008 ACM/IEEE conference on Supercomputing, November 15-21, 2008, Austin, Texas
	Ondřej Lhoták , Laurie Hendren, Evaluating the benefits of context-sensitive points-to analysis using a BDD-based implementation, ACM Transactions on Software Engineering and Methodology (TOSEM), v.18 n.1, p.1-53, September 2008
	David Eppstein, Testing bipartiteness of geometric intersection graphs, ACM Transactions on Algorithms (TALG), v.5 n.2, p.1-35, March 2009
	Omar Benjelloun , Hector Garcia-Molina , David Menestrina , Qi Su , Steven Euijong Whang , Jennifer Widom, Swoosh: a generic approach to entity resolution, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.1, p.255-276, January 2009
	Robert E. Shostak, An algorithm for reasoning about equality, Proceedings of the 5th international joint conference on Artificial intelligence, p.526-527, August 22-25, 1977, Cambridge, USA
	Hamish Carr , Jack Snoeyink , Michiel van de Panne, Flexible isosurfaces: Simplifying and displaying scalar topology using the contour tree, Computational Geometry: Theory and Applications, v.43 n.1, p.42-58, January, 2010
	Chavalit Likitvivatanavong , Yuanlin Zhang , James Bowen , Eugene C. Freuder, Maintaining arc consistency using adaptive domain ordering, Proceedings of the 19th international joint conference on Artificial intelligence, p.1527-1528, July 30-August 05, 2005, Edinburgh, Scotland