Martin Charles Golumbic

Research Statement

   I expect that I am best known internationally for my research contributions in algorithmic graph theory, which have steadily engaged much of my work for almost 30 years, and include a large variety of applications. My areas of research are in combinatorial algorithms and applied discrete mathematics interacting with real problems in computer science and artificial intelligence. This career-focused excursion into graphs and algorithms has taken me into fields as diverse as constraint-based scheduling, compiler design, circuit synthesis, temporal reasoning and biological applications.

   In all my published works, this central theme can be observed, of modeling, analyzing the mathematical structure, developing algorithms, evaluating the complexity and performance. I maintain my longstanding interest in perfect graphs, especially related to classes of intersection graphs, their algorithms and applications. This area of structured families of graphs has maintained its current and popular interest as witnessed by several recent workshops: Fields Institute (Toronto, May 2000), Dagstull (Germany, June 2001, May 2004), DIMACS (New Brunswick, July 2001), Southeastern Conference (Boca Raton, March 2004).

   My major impact in research, I believe, has been initially through my first book Algorithmic Graph Theory and Perfect Graphs (1980, second edition 2004), followed by what I consider to be my five most important papers in the area: J23 (trapezoid graphs), J16 (EPT graphs), J15 (tolerance graphs), J32 (sandwich problems), P17 (Boolean factorization). Their importance is that each of these were seminal works which spawned further research by other researchers and also myself. Certainly, many other of my papers are cited and have been expanded upon as well. I will mention them in what follows.

   My new book on the topic of Tolerance Graphs together with Prof. Ann Trenk, was published this year (Cambridge, 2004). This is a research book covering material from the journal and conference literature of the past 20 years, plus new results that have not appeared before. Other recent work has been on problems related to interval probe graphs (a subfamily of tolerance graphs motivated by molecular biology.

Inducibility of graphs: J1, P3, J10
This is a topic introduced by Nick Pippenger and myself in the 1970s. It has to do with the largest number of copies of a given graph which can appear in a larger graph. There are a small number of papers in the literature which have continued this work.

Sandwich problems: J32, J34-38
This is a topic Ron Shamir and I introduced first for interval graphs as part of our work on a temporal reasoning problem from artificial intelligence. It then took off when Ron made the connection with similar problems in computational biology. It has to do with the complexity of completing graphs (and later hypergraphs and 0/1 matrices) subject to a desired structural property and non-edge constraints.

Computer science and compiler design: J25, J31, J33 P2, P7, P4, J19
With Vladimir Rainish, we developed some novel instruction scheduling techniques both published and patented. In other work, as part of team, we developed new register allocation algorithms, building upon the classical approach of Chaitin, and which now appear in textbooks on compilers. My very early work on macro substitutions, which have something to do with interval and overlap graphs, solves problems which were independently discovered ten years later by the compression community (according to Tommy Klein).

Circuit synthesis and VLSI: J2, J23, P14, P17, P19, S1
Dagan, Pinter and I first studied the class of trapeziod graphs a dozen years ago in connection with a certain VLSI circuit problem. Trapeziod graphs generalize the classical family of interval graphs, and many papers have been written about them since. A related VLSI motivated problem on which Kaplan and I have worked is optimal cell flipping in permutation diagrams.

Even longer ago (two dozen years), I worked on some combinatorial merging problems also motivated by circuit design, and which generalized some methods of Huffman codes. Further work was done by Parker and by Knuth, and some of these notions are now being used and investigated at Berkeley and elsewhere for timing driven algorithms for minimization and delay estimation.

   Avi Mintz, in his doctoral thesis research with me, developed a novel method for factoring Boolean functions using graph partitioning. It also uses, as a subroutine at the lower levels of recursion, a very efficient method for factoring read-once functions which we developed with Udi Rotics using cographs and normality checking. These topics are also of interest in computational learning theory. We are also beginning to look at properties of read-twice functions, and have results on the read number for partial k-trees.

Artificial intelligence, constraint-based scheduling, temporal reasoning: J19, J26-28, P13, J32
My research in AI started with expert systems in a project between IBM and Bar-Ilan, then moved into constraint based scheduling with Ronen Feldman, and now is focused largely on temporal reasoning. I gave an invited short course lecture on this at the American Mathematics Society Winter Meeting (Jan. 1996), and invited talks on “Algorithmic Graph Theory in Temporal Reasoning” at the 28th Southeastern Conference on Combinatorics, Graph Theory and Computing (March 1997).

Tolerance graphs: P5, J15, R10, manuscript
This is a topic introduced by Clyde Monma and myself in 1982. It has its motivation with some scheduling problems, and is a generalization of both interval graphs and permutation graphs. Tom Trotter then joined us, and we obtained many basic results about the class. Many generalizations and variations on the theme of tolerance in graphs have been studied since, and as mentioned above, Ann Trenk and I have published a book on the topic (265 pages).

Other topics on graphs: J8, J42
Yehoshua Perl and I introduced the notion of Fibonacci maximum path graphs, which has been cited in a few subsequent papers. A recent doctoral thesis on this topic by Mark Kornblit was recently completed under the co-direction of Vadim Levit and myself. On another topic, Boros, Levit and I extended some results on the maximal stable sets of a graph.

Special matchings in graphs: J29, J39, J41
Renu Laskar and I looked at the problem of finding a special kind of matching, called an induced matching, in our paper on domination in circular arc graphs. Cameron had also worked on this problem. Moshe Lewenstein and I later obtained further algorithmic results on induced matchings in other families of graphs. Lewenstein and I also investigated a new topic in the area which we called uniquely restricted matchings. Gabow, Kaplan and Tarjan recently provided further results.

Special families of graphs:
All the other papers on my CV Besides the papers I have mentioned, the others deal with a variety of algorithmic and structural properties of graphs.