Earlier Research

Brenda S. Baker

These research areas and papers are listed approximately from more recent to less recent.

Algorithms for computational geometry and robotics

B. S. Baker, E. H. Grosse, and C. Rafferty, Non-obtuse Triangulation of Polygons, Discrete and Computational Geometry 3, 1988, pp. 147--168.

B. S. Baker, S. J. Fortune, and S. R. Mahaney, Polygon Containment under Translation, J. Algorithms 7,4, 1986, pp. 532--548.

B. S. Baker, S. J. Fortune, and E. H. Grosse, Stable Prehension with a Multi-Fingered Hand, Proc. Int'l Conf. on Robotics and Automation, March 1985, pp. 570--575.

B. S. Baker, S. J. Fortune, and E. H. Grosse, Stable Prehension with Three Fingers, Proc. 17th Symp. on Theory of Computing, 1985, pp. 114--120.

B. S. Baker, S. J. Fortune, and S. Mahaney, Inspection by Polygon Containment, Proc. of 22nd Annual Allerton Conf. on Communication, Control, and Computing, October, 1984.

CAD algorithms for VLSI

B. S. Baker, A Provably Good Algorithm for the Two Module Routing Problem, SIAM J. on Computing 15,1, February 1986, pp. 162--188.

B. S. Baker, S. N. Bhatt, and F. T. Leighton, An Approximation Algorithm for Manhattan Routing, Advances in Computing Research, Vol. 2: VLSI Theory (ed. F. Preparata), JAI Press, 1985.

B. S. Baker and R. Y. Pinter, An Algorithm for the Optimal Placement and Routing of a Circuit within a Ring of Pads, Proc. of 24th Annual Symp. on Foundations of Computer Science, 1983, pp. 360--370.

B. S. Baker, S. N. Bhatt, and F. T. Leighton, An Approximation Algorithm for Manhattan Routing, Proc. 15th Annual Symp. on Theory of Computing, 1983, pp. 477--486.

Algorithms for one- and two-dimensional packing problems

B. S. Baker, E. G. Coffman, Jr., and D. E. Willard, Algorithms for Allocating Fragmented Storage, J. ACM 32,2, April 1985, pp. 327--343.

B. S. Baker, A New Proof for the First-Fit Decreasing Bin-Packing Algorithm, J. Algorithms 6,1, March 1985, pp. 49--70.

B. S. Baker and E. G. Coffman, Jr., Insertion and Compaction Algorithms in Sequentially Allocated Storage, SIAM J. on Computing 13,3, August 1984, pp. 600--609.

B. S. Baker, A. R. Calderbank, E. G. Coffman, Jr., and J. C. Lagarias, Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle, SIAM J. on Algebraic and Discrete Methods 4,3, September 1983, pp. 383--397.

B. S. Baker and J. S. Schwarz, Shelf Algorithms for Two-Dimensional Packing Problems, SIAM J. Comp. 12,3, 1983, pp. 508--525.

B. S. Baker and E. G. Coffman, Jr., A Two Dimensional Bin-Packing Model of Preemptive, Fifo Storage Allocation, J. of Algorithms 3, 1982, pp. 303--316.

B. S. Baker, D. J. Brown, and H. P. Katseff, Lower Bounds for On-Line Two-Dimensional Packing Algorithms, Acta Informatica 18, 1982, pp. 207-225.

B. S. Baker and E.G. Coffman, Jr., A Tight Asymptotic Bound for Next-Fit-Decreasing Bin-Packing, SIAM J. on Algebraic and Discrete Methods 2,2, June 1981, pp. 147--152.

B. S. Baker, D. J. Brown, and H. P. Katseff, A 5/4 Algorithm for Two-Dimensional Packing, J. of Algorithms 2, 1981, pp. 348--368.

B. S. Baker, E. G. Coffman, Jr., and R. L. Rivest, Orthogonal Packings in Two Dimensions, SIAM J. on Computing 9,4, November 1980, pp. 846--855.

B. S. Baker, D. J. Brown, and H. P. Katseff, Lower Bounds for On-Line Two-Dimensional Packing Algorithms, Proc. Conf. on Inf. Sci. and Sys., March 1979, pp. 174-179.

B. S. Baker and J. S. Schwarz, Shelf Algorithms for Two-Dimensional Packing Problems, Proc. Conf. on Inf. Sci. and Sys., March 1979, pp. 273--276.

B. S. Baker and H. P. Katseff, The Up-Down Algorithm for Two-Dimensional Bin Packing, Proc. 17th Annual Allerton Conf. on Communication, Control, and Computing, October 1979.

B. S. Baker, E.G. Coffman, Jr., and R. L. Rivest, Orthogonal Packings in Two Dimensions, Proc. 16th Annual Allerton Conf. on Communication, Control, and Computing, October 1978, pp. 626--635.

Design of programming languages for structured programming

B. S. Baker and S. R. Kosaraju, A Comparison of Multilevel Break and Next Statements, J. ACM 26,3 , July 1979, pp. 555--566.

B.S. Baker and S. R. Kosaraju, A Comparison of Multilevel Break and Next Statements, Proc. Conf. on Information Sciences and Systems, 1977, pp. 213--218.

Reengineering unstructured programs

B.S. Baker, An Algorithm for Structuring Flowgraphs, J. ACM 24,1 , January, 1977, pp. 98--120.

B.S. Baker, An Algorithm for Structuring Programs: Extended Abstract, Proc. 3rd ACM Symposium on Principles of Programming Languages, January 1976, pp. 98-120.

Automata and formal language theory

B. S. Baker, Composition of Top-Down and Bottom-Up Tree Transductions, Info. and Control 41,2 , May 1979, 186--213.

B.S. Baker, Tree Transducers and Tree Languages, Info. and Control 37,3, June 1978, pp. 241--266.

B. S. Baker, Generalized Syntax-Directed Translation, Tree Transducers, and Linear Space, SIAM J. Comput. 7,3, August 1978, pp. 376--391.

B.S. Baker, Non-Context-Free Grammars Generating Context-Free Languages, Information and Control 24,3, March 1974, pp. 231--246.

B.S. Baker and R.V. Book, Reversal-Bounded Multipushdown Machines, J. Comp. Sys. Sci. 8,3, June 1974, pp. 315-332.

B. S. Baker, Tree Transductions and Families of Tree Languages, Ph.D. Dissertation, Harvard University, Cambridge, MA, 1973.

B. S. Baker, Tree Transductions and Families of Tree Languages, Proc. 5th Annual ACM Symp. on Theory of Computing, May 1973, pp. 200-206.

B. S. Baker and R.V. Book, Reversal-Bounded Multi-pushdown Machines, Proc. 13th Annual Symposium on Switching and Automata Theory, October 1972, pp. 207-211.

Distributed communication

B. S. Baker and R. Shostak, Gossips and Telephones, Discrete Math. 2,3, June 1972, 191-193.