Graph Algorithms and Theory Laboratory

Prof. Martin C. Golumbic, Director of Laboratory

Graph Theory

"Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications" Edited by Prof. Martin C. Golumbic (Director, CRI) and Dr. Irith Ben-Arroyo Hartman (CRI). For further details click here.

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, Prof. Ilan Newman, Dr. Yuri Rabinovich, Dr. Udi Rotics, Dr. Michal Stern and Prof. Alek Vainshtein; Graduate Students: Elad Cohen, Shimon Shrem and Guy Wolfovitz.


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 been: 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) and Stephen Smale (University of Chicago).


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
  • Computational aspects of metric spaces