Journal of the ACM Bibliography

Additional Key Words and Phrases: arithmetic expressions, compilation of arithmetic expressions, computational complexity, general arithmetic expressions, numerical stability, parallel computation, code optimization

Selected papers that cite this one

• A. Aggarwal, D. Kravets, J. K. Park, and S. Sen. Parallel searching in generalized Monge arrays. Algorithmica, 19(3):291-317, November 1997.

• Ravindra K. Ahuja, James B. Orlin, Clifford Stein, and Robert E. Tarjan. Improved algorithms for bipartite network flow. SIAM Journal on Computing, 23(5):906-933, October 1994.

• Alberto Apostolico and Dany Breslauer. An optimal O(log log n)-time parallel algorithm for detecting all squares in a string. SIAM Journal on Computing, 25(6):1318-1331, December 1996.

• Mikhail J. Atallah, Richard Cole, and Michael T. Goodrich. Cascading divide-and-conquer: A technique for designing parallel algorithms. SIAM Journal on Computing, 18(3):499-532, June 1989.

• E. Bampis, M. El Haddad, Y. Manoussakis, and M. Santha. A parallel reduction of Hamiltonian cycle to Hamiltonian path in tournaments. Journal of Algorithms, 19(3):432-440, November 1995.

• G. Bilardi and F. P. Preparata. Processor-time tradeoffs under bounded-speed message propogation: Part I, upper bounds. Theory of Computing Systems, 30(6):523-546, November/December 1997.

• Dario Bini and Victor Y. Pan. Computing matrix eigenvalues and polynomial zeros where the output is real. SIAM Journal on Computing, 27(4):1099-1115, August 1998.

• Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: An efficient multithreaded runtime system. Journal of Parallel and Distributed Computing, 37(1):55-69, 25 August 1996.

• Robert D. Blumofe and Charles E. Leiserson. Space-efficient scheduling of multithreaded computations. SIAM Journal on Computing, 27(1):202-229, February 1998.

• Maria Luisa Bonet and Samuel R. Buss. The serial transitive closure problem for trees. SIAM Journal on Computing, 24(1):109-122, February 1995.

• Dany Breslauer. Fast parallel string prefix-matching. Theoretical Computer Science, 137(2):269-278, 23 January 1995. Note.

• Nader H. Bshouty and Richard Cleve. Interpolating arithmetic read-once formulas in parallel. SIAM Journal on Computing, 27(2):401-413, March 1998.

• Nader H. Bshouty, Richard Cleve, and Wayne Eberly. Size-depth tradeoffs for algebraic formulas. SIAM Journal on Computing, 24(4):682-705, August 1995.

• Lin Chen. Optimal circular arc representations: Properties, recognition, and construction. Journal of Computer and System Sciences, 56(3):320-331, April 1998.

• Martin Dietzfelbinger, Miros{\l}aw Kuty{\l}owski, and Rüdiger Reischuk. Feasible time-optimal algorithms for Boolean functions on exclusive-write parallel random-access machines. SIAM Journal on Computing, 25(6):1196-1230, December 1996.

• David Eppstein. Parallel recognition of series-parallel graphs. Information and Computation, 98(1):41-55, May 1992.

• Greg N. Frederickson and Susan H. Rodger. An NC algorithm for scheduling unit-time jobs with arbitrary release times and deadlines. SIAM Journal on Computing, 23(1):185-211, February 1994.

• Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. The implementation of the Cilk-5 multithreaded language. In Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation (PLDI), pages 212-223, Montreal, Canada, 17-19 June 1998. SIGPLAN Notices 33(5), May 1998.

• Zvi Galil. A constant-time optimal parallel string-matching algorithm. Journal of the ACM, 42(4):908-918, July 1995.

• Li-Xin Gao and Arnold L. Rosenberg. Toward efficient scheduling of evolving computations on rings of processors. Journal of Parallel and Distributed Computing, 38(1):92-100, 10 October 1996.

• Phillip B. Gibbons, Yossi Matias, and Vijaya Ramachandran. Efficient low-contention parallel algorithms. Journal of Computer and System Sciences, 53(3):417-442, December 1996.

• Joseph Gil and Yossi Matias. An effective load balancing policy for geometric-decaying algorithms. Journal of Parallel and Distributed Computing, 36(2):185-188, 1 August 1996.

• Michael T. Goodrich. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences, 51(3):374-389, December 1995.

• Georg Gottlob. NP trees and Carnap's modal logic. Journal of the ACM, 42(2):421-457, March 1995.

• John Greiner and Guy E. Blelloch. A provably time-efficient parallel implementation of full speculation. In Conference Record of POPL '96: The 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 309-321, St. Petersburg Beach, Florida, 21-24 January 1996.

• Arvind Gupta and Naomi Nishimura. The parallel complexity of tree embedding problems. Journal of Algorithms, 18(1):176-200, January 1995.

• Shay Halperin and Uri Zwick. An optimal randomised logarithmic time connectivity algorithm for the EREW PRAM. Journal of Computer and System Sciences, 53(3):395-416, December 1996.

• Chin-Wen Ho, Sun-Yuan Hsieh, and Gen-Huey Chen. An efficient parallel strategy for computing K-terminal reliability and finding most vital edges in 2-trees and partial 2-trees. Journal of Parallel and Distributed Computing, 51(2):89-113, 15 June 1998.

• Costas S. Iliopoulos and Kunsoo Park. A work-time optimal algorithm for computing all string covers. Theoretical Computer Science, 164(1-2):299-310, 10 September 1996. Note.

• P. C. Kanellakis, D. Michailidis, and A. A. Shvartsman. Controlling memory access concurrency in efficient fault-tolerant parallel algorithms. Nordic Journal of Computing, 2(2):146-180, Summer 1995.

• Zvi M. Kedem, Gad M. Landau, and Krishna V. Palem. Parallel suffix-prefix-matching algorithm and applications. SIAM Journal on Computing, 25(5):998-1023, October 1996.

• C. E. Leiserson and K. H. Randall. Parallel algorithms for the circuit value update problem. Theory of Computing Systems, 30(6):583-597, November/December 1997.

• Yishay Mansour, Noam Nisan, and Uzi Vishkin. Trade-offs between communication throughput and parallel time. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 372-381, Montréal, Québec, Canada, 23-25 May 1994.

• Victor Y. Pan. Parallel computation of polynomial GCD and some related parallel computations over abstract fields. Theoretical Computer Science, 162(2):173-223, 20 August 1996.

• Victor Pan. Parallel solution of Toeplitzlike linear systems. Journal of Complexity, 8(1):1-21, March 1992.

• V. Y. Pan. New resultant inequalities and complex polynomial factorization. SIAM Journal on Computing, 23(5):934-950, October 1994.

• Victor Y. Pan and Franco P. Preparata. Work-preserving speed-up of parallel matrix computations. SIAM Journal on Computing, 24(4):811-821, August 1995.

• D. B. Skillicorn. Deriving parallel programs from specification susing cost information. Science of Computer Programming, 20(3):205-221, June 1993.

• Thomas H. Spencer. Time-work tradeoffs for parallel algorithms. Journal of the ACM, 44(5):742-778, September 1997.

• Mikkel Thorup. Parallel shortcutting of rooted trees. Journal of Algorithms, 23(1):139-159, April 1997.

• Pilar de la Torre and Clyde P. Kruskal. Fast parallel algorithms for all-sources lexicographic search and path-algebra problems. Journal of Algorithms, 19(1):1-24, July 1995.

Selected references

• James C. Beatty. An axiomatic approach to code optimization for expressions. Journal of the ACM, 19(4):613-640, October 1972.

• Ian Munro and Michael Paterson. Optimal algorithms for parallel polynomial evaluation. In Conference Record 1971 Twelfth Annual Symposium on Switching and Automata Theory, pages 132-139, East Lansing, Michigan, 13-15 October 1971. IEEE.

Shortcuts: