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.