Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear-time pointer-machine algorithms for least common ancestors, MST verification, and dominators

Full text

Pdf (1.29 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 279 - 288

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Adam L. Buchsbaum	AT&T Labs, 180 Park Ave., Florham Park, NJ
Haim Kaplan	AT&T Labs, 180 Park Ave., Florham Park, NJ
Anne Rogers	AT&T Labs, 180 Park Ave., Florham Park, NJ
Jeffery R. Westbrook	AT&T Labs, 180 Park Ave., Florham Park, NJ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 35, Citation Count: 9

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/276698.276764 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	3	S. Alstrup, D. Harel, P. W. Lauridsen, and M. Thorup. Dominators in linear time. Manuscript submitted, 1997.
	4	Stephen Alstrup , Jens Peter Secher , Maz Spork, Optimal on-line decremental connectivity in trees, Information Processing Letters, v.64 n.4, p.161-164, Nov. 28, 1997 [doi>10.1016/S0020-0190(97)00170-1]
	5	A. L. Buchsbaum, H. Kaplan, A. Rogers, and J. R. Westbrook. A new, simpler linear-time dominators algorithm. Technical Report 97.31.2, AT&T Labs- Research, 1998. Submitted for publication.
	6	Adam L. Buchsbaum , Rajamani Sundar , Robert E. Tarjan, Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended Queues, SIAM Journal on Computing, v.24 n.6, p.1190-1206, Dec. 1995 [doi>10.1137/S0097539792242144]
	7	Bernard Chazelle, A Faster Deterministic Algorithm for Minimum Spanning Trees, Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS '97), p.22, October 19-22, 1997
	8	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	9	Brandon Dixon , Monika Rauch , Robert E. Tarjan, Verification and sensitivity analysis of minimum spanning trees in linear time, SIAM Journal on Computing, v.21 n.6, p.1184-1192, Dec. 1992 [doi>10.1137/0221070]
	10	B. Dixon and R. E. Tarjan. Optimal parallel verification of minimum spanning trees in logarithmic time. Algorithmica, 17:11-8, 1997.
	11	Yossi Shiloach , Shimon Even, An On-Line Edge-Deletion Problem, Journal of the ACM (JACM), v.28 n.1, p.1-4, Jan. 1981 [doi>10.1145/322234.322235]
	12	Jeanne Ferrante , Karl J. Ottenstein , Joe D. Warren, The program dependence graph and its use in optimization, ACM Transactions on Programming Languages and Systems (TOPLAS), v.9 n.3, p.319-349, July 1987 [doi>10.1145/24039.24041]
	13	Michael L. Fredman , Dan E. Willard, Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, v.48 n.3, p.533-551, June 1994 [doi>10.1016/S0022-0000(05)80064-9]
	14	H. N. Gabow and R. E. Tarjan. A linear-time algorithm for a special case of disjoint set union. JCSS, 30(2):209-21, 1985.
	15	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 [doi>10.1145/22145.22166]
	16	Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
	17	David R. Karger , Philip N. Klein , Robert E. Tarjan, A randomized linear-time algorithm to find minimum spanning trees, Journal of the ACM (JACM), v.42 n.2, p.321-328, March 1995 [doi>10.1145/201019.201022]
	18	V. King. A simpler minimum spanning tree verification algorithm. Algorithmica, 18:263-70, 1997.
	19	J. Koml6s. Linear verification for spanning trees. Combinatorica, 5(1):57-65, 1985.
	20	Thomas Lengauer , Robert Endre Tarjan, A fast algorithm for finding dominators in a flowgraph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.121-141, July 1979 [doi>10.1145/357062.357071]
	21	Martin Loebl , Jaroslav Nešetřil, Linearity and unprovability of set union problem strategies I: linearity of strong postorder, Journal of Algorithms, v.23 n.2, p.207-220, May. 1997 [doi>10.1006/jagm.1996.0815]
	22	Edward S. Lowry , C. W. Medlock, Object code optimization, Communications of the ACM, v.12 n.1, p.13-22, Jan. 1969 [doi>10.1145/362835.362838]
	23	Joan M. Lucas, Postorder disjoint set union is linear, SIAM Journal on Computing, v.19 n.5, p.868-882, Oct. 1990 [doi>10.1137/0219060]
	24	Paul W. Purdom, Jr. , Edward F. Moore, Immediate predominators in a directed graph [H], Communications of the ACM, v.15 n.8, p.777-778, Aug. 1972 [doi>10.1145/361532.361566]
	25	Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
	26	R. E. Tarjan. Finding dominators in directed graphs. SIAM J. Comp., 3(1):62-89, 1974.
	27	Robert Endre Tarjan, Applications of Path Compression on Balanced Trees, Journal of the ACM (JACM), v.26 n.4, p.690-715, Oct. 1979 [doi>10.1145/322154.322161]
	28	R. E. Tarjan. A class of algorithms which require nonlinear time to maintain disjoint sets. JCSS, 18(2): 110- 27, 1979.
	29	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 [doi>10.1145/62.2160]

CITED BY 9

	Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery R. Westbrook, A new, simpler linear-time dominators algorithm, ACM Transactions on Programming Languages and Systems (TOPLAS), v.20 n.6, p.1265-1296, Nov. 1998
	Seth Pettie , Vijaya Ramachandran, Computing shortest paths with comparisons and additions, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.267-276, January 06-08, 2002, San Francisco, California
	Seth Pettie , Vijaya Ramachandran, An optimal minimum spanning tree algorithm, Journal of the ACM (JACM), v.49 n.1, p.16-34, January 2002
	Loukas Georgiadis , Robert E. Tarjan, Finding dominators revisited: extended abstract, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Loukas Georgiadis , Robert E. Tarjan, Dominator tree verification and vertex-disjoint paths, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
	Gianfranco Bilardi , Keshav Pingali, Algorithms for computing the static single assignment form, Journal of the ACM (JACM), v.50 n.3, p.375-425, May 2003
	A. Dal Palú , E. Pontelli , D. Ranjan, Sequential and parallel algorithms for the NCA problem on pure pointer machines, Theoretical Computer Science, v.352 n.1, p.108-135, 7 March 2006
	Seth Pettie , Vijaya Ramachandran, Randomized minimum spanning tree algorithms using exponentially fewer random bits, ACM Transactions on Algorithms (TALG), v.4 n.1, p.1-27, March 2008
	Pierre Charbit , Michel Habib , Vincent Limouzy , Fabien de Montgolfier , Mathieu Raffinot , Michaël Rao, A note on computing set overlap classes, Information Processing Letters, v.108 n.4, p.186-191, October, 2008