Martin Charles Golumbic (born 1948) [1] is a mathematician and computer scientist known for his research on perfect graphs, graph sandwich problems, compiler optimization, and spatial-temporal reasoning. He is a professor emeritus of computer science at the University of Haifa, [2] and was the founder of the journal Annals of Mathematics and Artificial Intelligence.
Golumbic majored in mathematics at Pennsylvania State University, graduating in 1970 with bachelor's and master's degrees. [3] He completed his Ph.D. at Columbia University in 1975, with the dissertation Comparability Graphs and a New Matroid supervised by Samuel Eilenberg. [4]
He became an assistant professor in the Courant Institute of Mathematical Sciences of New York University from 1975 until 1980, when he moved to Bell Laboratories. From 1983 to 1992 he worked for IBM Research in Israel, and from 1992 to 2000 he was a professor of mathematics and computer science at Bar-Ilan University. He moved to the University of Haifa in 2000, where he founded the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science. [3] [2]
In 1989, Golumbic founded the Bar-Ilan Symposium in Foundations of Artificial Intelligence, a leading artificial intelligence conference in Israel. [5] In 1990 Golumbic became the founding editor-in-chief of the journal Annals of Mathematics and Artificial Intelligence, published by Springer. [6]
Golumbic is a fellow of the European Association for Artificial Intelligence (2005). [7] He was elected to the Academia Europaea in 2013.
At the 2019 Bar-Ilan Symposium in Foundations of Artificial Intelligence, Golumbic was given the Lifetime Achievement and Service Award of the Israeli Association for Artificial Intelligence. [5]
Golumbic is the author of books including:
Other highly-cited publications of Golumbic include:
In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals.
In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.
In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.
In the mathematical discipline of graph theory, a feedback vertex set (FVS) of a graph is a set of vertices whose removal leaves a graph without cycles. Equivalently, each FVS contains at least one vertex of any cycle in the graph. The feedback vertex set number of a graph is the size of a smallest feedback vertex set. The minimum feedback vertex set problem is an NP-complete problem; it was among the first problems shown to be NP-complete. It has wide applications in operating systems, database systems, and VLSI chip design.
In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.
In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.
In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979).
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.
In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.
In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.
In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph.
Eliahu (Eli) Shamir is an Israeli mathematician and computer scientist, the Jean and Helene Alfassa Professor Emeritus of Computer Science at the Hebrew University of Jerusalem.
In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by Bruno Courcelle in 1990 and independently rediscovered by Borie, Parker & Tovey (1992). It is considered the archetype of algorithmic meta-theorems.
Ron Shamir is an Israeli professor of computer science known for his work in graph theory and in computational biology. He holds the Raymond and Beverly Sackler Chair in Bioinformatics, and is the founder and head of the Edmond J. Safra Center for Bioinformatics at Tel Aviv University.
In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.
Jorge Urrutia Galicia is a Mexican mathematician and computer scientist in the Institute of Mathematics of the National Autonomous University of Mexico (UNAM). His research primarily concerns discrete and computational geometry.
In graph theory, a tolerance graph is an undirected graph in which every vertex can be represented by a closed interval and a real number called its tolerance, in such a way that two vertices are adjacent in the graph whenever their intervals overlap in a length that is at least the minimum of their two tolerances. This class of graphs was introduced in 1982 by Martin Charles Golumbic and Clyde Monma, who used them to model scheduling problems in which the tasks to be modeled can share resources for limited amounts of time.
Zvi Lotker is an Israeli computer scientist and communications systems engineer who works in the fields of digital humanities, artificial intelligence, distributed computing, network algorithms, and communication networks. He is an associate professor in the Alexander Kofkin Faculty of Engineering at Bar-Ilan University.
Helmut Alt is a German computer scientist whose research concerns graph algorithms and computational geometry. He is known for his work on matching geometric shapes, including methods for efficiently computing the Fréchet distance between shapes. He was also the first to use the German phrase "Algorithmische Geometrie" [algorithmic geometry] to refer to computational geometry. He is a professor of computer science at the Free University of Berlin.
| General | |
|---|---|
| National libraries | |
| Scientific databases | |
| Other | |
