Other Research

Brenda S. Baker

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

Internet Content Filtering

Brenda S. Baker and Eric Grosse, Local Control over Filtered Access to the WWW, Proceedings of Fourth World Wide Web Conference, December, 1995, Boston, MA. Also WWW J. 1,1, Jan., 1996. gzipped PostScript.

Graph Algorithms

Brenda S. Baker and Edward G. Coffman, Jr., Mutual Exclusion Scheduling, Theoretical Computer Science 162,2, Aug., 1996, pp. 225-243.

Brenda S. Baker, Approximation Algorithms for NP-complete Problems on Planar Graphs, J. ACM 41,1, Jan., 1994, pp. 153-180. gzipped PostScript.

Brenda S. Baker, Approximation Algorithms for NP-complete Problems on Planar Graphs (Extended Abstract), Proc. of 24th Annual Symp. on Foundations of Comp. Sci. (FOCS), 1983, pp. 265-273.

Algorithms for computational geometry and robotics

Brenda S. Baker, Eric Grosse, and Conor S. Rafferty, Nonobtuse 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.

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

Brenda S. Baker, Steven Fortune, and Eric Grosse, Stable Prehension with Three Fingers, Proc. 17th Symp. on Theory of Computing, 1985, pp. 114--120.

Brenda 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

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

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

Brenda S. Baker and Ron Y. Pinter, An Algorithm for the Optimal Placement and Routing of a Circuit within a Ring of Pads (Extended Abstract), Proc. of 24th Annual Symp. on Foundations of Computer Science (FOCS), 1983, pp. 360--370.

Brenda S. Baker, Sandeep N. Bhatt, and Frank Thomson Leighton, An Approximation Algorithm for Manhattan Routing (Extended Abstract), Proc. 15th Annual Symp. on Theory of Computing (STOC), 1983, pp. 477--486.

Algorithms for one- and two-dimensional packing problems

Brenda S. Baker, Edward G. Coffman, Jr., and Dan E. Willard, Algorithms for Resolving Conflicts in Dynamic Storage Allocation, J. ACM 32,2, April 1985, pp. 327--343.

Brenda 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.

Brenda 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.

Donna J. Brown, Brenda S. Baker, and Howard 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.

Brenda 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.

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

Brenda 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.

Brenda 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

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

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

Reengineering unstructured programs

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

Brenda 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

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

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

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

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

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

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

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

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

Distributed communication

Brenda Baker and Robert Shostak, Gossips and Telephones, Discrete Math. 2,3, June 1972, 191-193.


Home

Last modified: Sat Jan 22 21:16:12 PST 2011
© 2011 Brenda S. Baker. All rights reserved.