Robert Endre Tarjan
- 1 kCKERMANN, W Zum Hllbertshen Aufbau der reelen Zahlen Math. Ann. 99 (1928), 118-133.Google Scholar
- 2 AHO, A. V , HOPCROFT, J. E , AND ULLMAN, J D On computing least common ancestors in trees. Proc 5th Annual ACM Symp. on Theory of Computing, Austin, Texas, 1973, pp. 253-265 Google Scholar
- 3 ARDEN, B. W , GALLER, B. A , AND GRAHAM, R M. An algorithm for equivalence declarations. Comm. ACM 4, 7 (July 1961), 310-314. Google Scholar
- 4 CHV~.TAL, V., KLARNER, D. A , AND KNUTH, D E. Selected combinatorial research problems Tech Rep STAN-CS-72-292, Comput. Sci Dep, Stanford U., Stanford, Cahf, 1972. Google Scholar
- 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.Google Scholar
- 6 GALLER, B.A ,AND FISCHER, M.J. An lmproved equivalence algorithm Comm. ACM 7,5 (May 1964), 301-303. Google Scholar
- 7 HOPCROFT, J , AND ULLMAN, J.D. Set-mergmg algorithms. SIAM J. Comput ~ (Dec. 1973), 294-303.Google Scholar
- 8 HOPCROFT, J Private communication.Google Scholar
- 9 KERSCHENBAUM, A, AND VAN SLYKE, R Computing minimum spanning trees efficiently. Proc 25th Annual Conf of the ACM, 1972, p.p 518-527. Google Scholar
- 10 ~NUTH, D.E. The Art of Computer Programming, Vol. I: FundamenLal Algorithms. Addison- Wesley, Reading, Mass, 1969, pp 353-355. Google Scholar
- 11 PATERSON, M. Unpublished report, U. of Warwick, Coventry, Great Britain.Google Scholar
- 12 STEARNS, R E., AND ROSENKRANTZ, D. J. Table machine simulation. 1Oth Annum SWAT Conf. Proc, 1969, pp 118-128.Google Scholar
- 13 TARJAN, R Testing flow graph reducibility. Proc 5th Annual ACM Syrup. on Theory of Computing, Austin, Texas, 1973, pp. 96-107 Google Scholar
- 14 TARJAN, R. Finding dominators in directed graphs SIAM J Comput. S (March 1974), 62-89.Google Scholar
Index Terms
- Efficiency of a Good But Not Linear Set Union Algorithm
Recommendations
An optimal algorithm for computing the non-trivial circuits of a union of iso-oriented rectangles
Given n rectangles R"1,...,R"n on the plane with sides parallel to the coordinate axes, Lipski and Preparata (1981) [1] have presented a @Q(nlogn) time and O(nlogn) space algorithm for computing the non-trivial circuits of the union U=R"1@?...@?R"n. In ...
A linear-time algorithm for a special case of disjoint set union
STOC '83: Proceedings of the fifteenth annual ACM symposium on Theory of computingThis paper presents a linear-time algorithm for the special case of the disjoint set union problem in which the structure of the unions (defined by a “union tree”) is known in advance. The algorithm executes an intermixed sequence of m union and find ...
A linear-time algorithm for constructing a circular visibility diagram
To computer circular visibility inside a simple polygon, circular arcs that emanate from a given interior point are classified with respect to the edges of the polygon they first intersect. Representing these sets of circular arcs by their centers ...
Comments