M. Tompa
- [1] A. Aggarwal and R. Anderson. A random NC algorithm for depth first search. Combinatorica, 8(1):1-12, 1988.Google Scholar
Cross Ref
- [2] N. Alon and Y. Azar. Parallel comparison algorithms for approximation problems. In 29th, Annual Symposium on Foundations of Computer Science, pages 194-203, White Plains, New York, October 1988.Google Scholar
- [3] R. Bar-Yehuda and S. Even. A linear-time approximation algorithm for the weighted vertex cover problem. Journal of Algorithms, 2:198-203, 1981.Google ScholarCross Ref
- [4] C. Beeri, A. O. Mendelzon, Y. Sagiv, and J. D. Ullman. Equivalence of relational database schemes. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, pages 319-329, Atlanta, Georgia, April-May 1979. Google ScholarDigital Library
- [5] S. Bhatt and J.-Y. Cai. Take a walk, grow a. tree. In 29th, Annual Symposium on Foundations of Computer Science, pages 469-478, White Plains, New York, October 1988.Google Scholar
- [6] A. Borodin and S. Cook. A time-space tradeoff for sorting on a general sequential model of computation. SIAM Journal on Computing, 12(2):287-297, May 1982.Google ScholarCross Ref
- [7] G. Brassard and P. Bratley. Algorithmics: Theory and Practice. Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1988. Google ScholarDigital Library
- [8] G. Brassard and C. Crépeau. Non-transitive transfer of confidence: a perfect zero-knowledge interactive protocol for SAT and beyond. In 27th Annual Symposium on Foundations of Computer Science, pages 188-195, Toronto, Ontario, October 1986.Google ScholarDigital Library
- [9] P. Erdös, R. L. Graham, and E. Szemerédi. On sparse graphs with dense long paths. Comp. and Maths. with Appls., 1:365-369, 1975.Google ScholarCross Ref
- [10] M. R. Garey, R. L, Graham, and D. S. Johnson. Some NP-complete geometric problems. In Proceedings of the Eighth Annual ACM Symposium on Theory of Computing, pages 10-22, Hershey, Pennsylvania, May 1976. Google ScholarDigital Library
- [11] R. L. Graham, E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey. In P. L. Hammer, E. L. Johnson, and B. H. Korte, editors, Discrete Oplimization II, Annals of Discrete Mathematics, 5, pages 287-326, North-Holland Publishing Company, Amsterdam, 1979.Google Scholar
- [12] J. Kahn, M. Klawe, and P. Kleitman. Traditional galleries require fewer watchmen, SIAM J. Alg. Disc. Meth., 4:194-206, 1980.Google ScholarCross Ref
- [13] N. Karmarkar, R. Karp, R. Lipton, L. Lovász, and M. Luby. A Monte Carlo Algorithm to Approximate the Permanent. Technical Report, University of Toronto, 1988.Google Scholar
- [14] H. T. Kung and C. E. Leiserson. Algorithms for VLSI processor arrays. In Symposium on Sparse Matrix Computations and Their Applications, November 1978.Google Scholar
- [15] R. E. Ladner and N. A. Lynch. Relativization of questions about log space computability. Mathematical Systems Theory, 10(1):19-32, 1976.Google ScholarCross Ref
- [16] E. L. Lawler, R. E. Tarjan, and J. Valdes. Analysis and isomorphism of series parallel digraphs. 1982. Eventually appeared as [33].Google Scholar
- [17] F. T. Leighton and C. E. Leiserson. Wafer-scale integration of systolic arrays. In 23rd Annual Symposium on Foundations of Computer Science, pages 297-311, Chicago, Illinois, November 1982.Google ScholarDigital Library
- [18] A. K. Lenstra, H. W. Lenstra, and Lovász L. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:513-534, 1982.Google ScholarCross Ref
- [19] W. F. Ogden, W. E. Riddle, and W. C. Rounds. Complexity of expressions allowing concurrency. In Conference Record of the Fifth Annual ACM Symposium on Principles of Programming Languages, pages 185-194, 1978. Google ScholarDigital Library
- [20] W. J. Paul, N. Pippenger, E. Szemerédi, and W. T. Trotter. On determinism versus non-determinism and related problems. In 24th Annual Symposium on Foundations of Computer Science, pages 429-438, Tucson, Arizona, November 1983.Google ScholarDigital Library
- [21] W. J. Paul, E. J. Prauß, and R. Reischuk. On alternation. Acta Informatica, 14:243- 255, 1980.Google ScholarDigital Library
- [22] W. J. Paul and R. Reischuk. On alternation II. Acta Informatica, 14:391-403, 1980.Google ScholarDigital Library
- [23] W. J. Paul, J. I. Seiferas, and J. Simon. An information theoretic approach to time bounds for on-line computation. Journal of Computer and System, Sciences, 23:108- 126, 1981.Google Scholar
- [24] W. J. Paul and R. E. Tarjan. Time-space trade-offs in a. pebble game. Acta Informatica , 10:111-115, 1978.Google ScholarDigital Library
- [25] W. J. Paul, R. E. Tarjan, and J. R. Celoni. Space bounds for a game on graphs. Mathematical Systems Theory, 10:239-251, 1977.Google ScholarCross Ref
- [26] B. Plumstead and J. Plumstead. Bounds for cube coloring. SIAM J. Alg. Disc. Meth., 6(1), January 1985.Google ScholarCross Ref
- [27] W. L. Ruzzo, J. Simon, and M. Tompa. Space-bounded hierarchies and probabilistic computations. Journal of Computer and System Sciences, 28(2):216-230, April 1984.Google ScholarCross Ref
- [28] N. Santoro, J. B. Sidney, S. J. Sidney, and J. Urrutia. Geometric containment and vector dominance. Theoretical Computer Science, 53:345-352, 1987. Google ScholarDigital Library
- [29] J. T. Schwartz, M. Sharir, and A. Siegel. An Efficient Algorithm for Finding Connected Components in a Binary Image. Technical Report TR. 154, New York University, New York, New York, 1985.Google Scholar
- [30] E. Shamir and M. Snir. On the depth complexity of formulas. Mathematical Systems Theory, 13:301-322, 1980.Google ScholarCross Ref
- [31] R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM Journal on Computing, 6(1):84-85, March 1977.Google ScholarCross Ref
- [32] R. E. Tarjan and U. Vishkin. An efficient, parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862-874, November 1985.Google ScholarCross Ref
- [33] J. Valdes, R. E. Tarjan, and E. L. Lawler. The recognition of series parallel digraphs. SIAM Journal on Computing, 11:298-313, 1982.Google ScholarCross Ref
- [34] U. Vazirani and V. Vazirani. Random polynomial time is equal to slightly-random polynomial time. In 26th Annual Symposium on Foundations of Computer Science, pages 417-428, Portland, Oregon, October 1985.Google ScholarDigital Library
- [35] U. Vishkin and A. Wigderson. Trade-offs between depth and width in parallel computation. SIAM Journal on Computing, 14(2):303-314, May 1985.Google ScholarCross Ref
- [36] C. K. Wong and A. C. Yao. A combinatorial optimization problem related to data set allocation. Rev. Francaise Automat. Informat. Recherche Operationnelle Ser. Bleue, 10.5 (suppl.):83-95, 1976.Google Scholar
- [37] D. Wood and C. K. Yap. Computing a convex skull of an orthogonal polygon. In Proceedings of the First Annual ACM Symposium on Computational Geometry, pages 311-315, 1985. Google ScholarDigital Library
- [38] A. C. Yao and F. F. Yao. A general approach to geometric queries. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 163-168, Providence, Rhode Island, May 1985. Google ScholarDigital Library
Index Terms
- Figures of merit
Recommendations
New figures of merit for best-first probabilistic chart parsing
Best-first parsing methods for natural language try to parse efficiently by considering the most likely constituents first. Some figure of merit is needed by which to compare the likelihood of constituents, and the choice of this figure has a ...
Developing figures of merit for determining relative air quality
WSC '83: Proceedings of the 15th conference on Winter Simulation - Volume 2In spite of the fact that air quality has been a major national concern for many years measures have not been taken to develop a methodology for evaluating the relative merit of air quality alternatives. The research to be presented explores the issue ...
A one-parametric class of merit functions for the second-order cone complementarity problem
We investigate a one-parametric class of merit functions for the second-order cone complementarity problem (SOCCP) which is closely related to the popular Fischer---Burmeister (FB) merit function and natural residual merit function. In fact, it will ...
Comments