Research Interests: Graph Theory

Most of my work in graph theory has been in the area of stack and queue layouts of undirected graphs, directed acyclic graphs (dags), and partially ordered sets (posets). In collaboration with Lenwood S. Heath, Department of Computer Science, at Virginia Tech, I have derived algorithmic and combinatorial results in this area. Our results have implications in the areas of fault-tolerant VLSI design, scheduling of parallel processors, systolic arrays, and graph drawing. What follows is a list of papers (in postscript format) that contain most of the results mentioned above.

• Stack and Queue Layouts of Dags -- Part I
  Lenwood S. Heath, Sriram V. Pemmaraju, and Ann Trenk. Accepted for publication in the SIAM Journal on Computing, 1996.
• Stack and Queue Layouts of Dags -- Part II
  Lenwood S. Heath and Sriram V. Pemmaraju. Accepted for publication in the SIAM Journal on Computing, 1996.
• Stack and Queue Layouts of Posets
  Lenwood S. Heath and Sriram V. Pemmaraju, Accepted for publication in the SIAM Journal on Discrete Mathematics.
• Recognizing Leveled-Planar Dags in Linear Time
  Lenwood S. Heath and Sriram V. Pemmaraju, Proceedings of Graph Drawing 1995, 1996, pp. 300--311.
• Stack and Queue Layouts of Directed Acyclic Graphs
  Ann Trenk Barrett, Lenwood S. Heath, and Sriram V. Pemmaraju. Extended abstract appeared in the Proceedings of the DIMACS Workshop on Planar Graphs: Structure and Algorithms, William T. Trotter, editor, American Mathematical Society, Providence, Rhode Island, 1993, pages 5--11.
• Queue Layouts and Matrix Covers
  Lenwood S. Heath and Sriram V. Pemmaraju, Virginia Tech, TR 94-22. Submitted for publication.
• Sparse Matrix-Vector Multiplication on a Small Linear Array
  Lenwood S. Heath, Sriram V. Pemmaraju, and Calvin J. Ribbens, University of Iowa, TR 93-11. Submitted for publication.

More recently, I have worked on problems related to compiler construction that can be modeled as graph-theoretic problems. Papers that describe this work are listed below:

• Using Graph Coloring in an Algebraic Compiler
  Teodor Rus and Sriram V. Pemmaraju, Acta Informatica 34, 191-209 (1997).
• 
  Automatic Data Decomposition for Message-Passing Machines
  Mirela Damian-Iordache and Sriram V. Pemmaraju. To be presented at the The 10th International Workshop on Languages and Compilers for Parallel Computing, August 7-11, Minneapolis, MN.
  Here is a longer version that contains the proofs (also available as Technical Report TR 97-01, Department of Computer Science, The University of Iowa).

• Combinatorica is a package running under Mathematica, comprising over 230 functions for combinatorics and graph theory. It is best described in the following book by Steven Skiena:
  Implementing Discrete Mathematics: Combinatorics and Graph Theory in Mathematica, Advanced Book Division, Addison-Wesley, Redwood City CA, June 1990. ISBN number 0-201-50943-1.

• Link is a software system for discrete mathematics, that was created as part of a DIMACS project.

• LEDA (Library of Efficient Datatypes and Algorithms) is a collection of C++ classes and combinatorial algorithms implemented in C++. Examples of data types that are implemented in LEDA are: red-black trees, Fibonacci heaps, and dynamic perfect hash tables.

• Stanford Graphbase created by Donald Knuth is a wonderful collection of datasets and computer programs that generate and examine a wide variety of graphs and networks. The computer programs are written a CWEB, a combination of the C language and the TeX typesetting system. The language CWEB allows what Knuth calls "literate programs". Stanford Graphbase is described in a book by Donald Knuth: The Stanford Graphbase: A Platform for Combinatorial Computing, ACM Press, New York, NY and Addison-Wesley Publishing Company, Reading, MA.

• A collection of algorithmic complexity results for various graph families can be found here.