Graph Algorithms and Theory Laboratory

Prof. Martin C. Golumbic, Director of Laboratory

This laboratory carries out research in the areas of graph theory, algorithms and theory of computation. Graph theory is a sub-field of combinatorics, a relatively new discipline, developed extensively within the past fifty years, which deals with finite structures and the relationship between their elements. Graph theory serves as a theoretical basis for computer science.

Theoretical computer science involves research on the complexity of algorithms and various models of computation. This includes the design of efficient algorithms, parallel models, combinatorial optimization and randomized algorithms. Two weekly seminar series which meet throughout the academic year are sponsored by the laboratory.

The laboratory is headed by Prof. Martin C. Golumbic and includes: Dr. Andrei Asinowski, Dr. Irith Ben-Arroyo Hartman, Dr. Eli Berger, Dr. Marina Lipshteyn, Dr. Gila Morgenstern; Prof. Ilan Newman, Prof. Yuri Rabinovich, Dr. Michal Stern, Prof. Alek Vainshtein and Prof. Oren Weimann; Graduate Students: Rowaida Mahameed and Ofer Magen.

Since its inception in 2001, CRI has become a leading national forum in the field of graph theory, combinatorics and algorithms. Every year, the laboratory organizes the “Haifa Workshop on Interdisciplinary Applications of Graph Theory, Combinatorics and Algorithms.” This conference attracts top researchers from Israel and around the world. It has resulted in the publication of books and special issues of professional journals. The keynote speakers since 2001 have included: Richard Karp (University of California, Berkeley), Robert Tarjan (Princeton University), Peter Hammer (Rutgers, The State University of New Jersey), Andrew Yao (Princeton University), Michael Rabin (Harvard University and Hebrew University), Michel Goemans (Massachusetts Institute of Technology), Adi Shamir (Weizmann Institute of Science), Stephen Smale (University of Chicago), Bela Bollobas (Univ. of Cambridge and Univ. of Memphis) and Daniel Spielman (Yale Univ.).

Current research activities of the laboratory include:

• Combinatorial mathematics of path partitions in directed graphs
• Algorithms and applications of structured families of intersection graphs
• Tolerance graph problems
• Boolean functions
• Combinatorial property testing and randomized algorithms
• Algorithms for planar graphs
• Computational aspects of metric spaces