This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
(Learn how and when to remove this template message) |

**Martin Charles Golumbic** (born September 30, 1948) is a mathematician and computer scientist, best known for his work in algorithmic graph theory and in artificial intelligence. He is the founding editor-in-chief of the journal *Annals of Mathematics and Artificial Intelligence*, published by Springer.^{ [1] }

Golumbic was born in 1948 in Erie, Pennsylvania, U.S. He received his Ph.D. in 1975 at Columbia University, where his advisor was Samuel Eilenberg.^{ [2] } He was a professor at the Courant Institute of Mathematical Sciences of New York University until 1980, and then a researcher at Bell Laboratories until moving permanently to Israel in 1982, where he previously held positions at IBM Research and Bar-Ilan University. Golumbic is the founder and director emeritus of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He has held visiting positions at Université de Paris, the Weizmann Institute of Science, the École Polytechnique Fédérale de Lausanne, the Universidade Federal do Rio de Janeiro, Columbia University, Rutgers University, the Indian Institute of Technology Kharagpur, Tsinghua University, and the University of New South Wales.

Golumbic was elected a fellow of the Institute of Combinatorics and its Applications (1995), fellow of the European Association for Artificial Intelligence (2005), and member of the Academia Europaea, honoris causa (2013). Golumbic also served as chairman of the Israeli Association of Artificial Intelligence (1998–2004), and founded and chaired numerous international symposia in discrete mathematics and in the foundations of artificial intelligence.

He is the author of several books including *Algorithmic Graph Theory and Perfect Graphs*, *Tolerance Graphs* (with Ann Trenk) and *Fighting Terror Online: The Convergence of Security, Technology, and the Law*.

Golumbic's work in graph theory lead to the study of new perfect graph families such as tolerance graphs, which generalize the classical graph notions of interval graph and comparability graph. He is credited with introducing the systematic study of algorithmic aspects in intersection graph theory, and initiated research on new structured families of graphs including the edge intersection graphs of paths in trees, tolerance graphs, chordal probe graphs and trivially perfect graphs. Golumbic, Kaplan and Shamir introduced the study of graph sandwich problems.

In the area of compiler optimization, Golumbic holds a joint patent with Vladimir Rainish, *Instruction Scheduler for a Computer*, (UK9-90-035/IS), an invention based on their technique called SHACOOF (ScHeduling Across COntrOl Flow), which in Hebrew means "transparent". He has contributed to the development of fundamental research in artificial intelligence in the area of complexity and spatial-temporal reasoning.

- 1966 Rensselaer Medal for Excellence in Mathematics
- 1991 Institute of Combinatorics and its Applications, Foundation Fellow
- 2005 European Coordinating Committee for Artificial Intelligence, ECCAI Fellow
- 2013 Academia Europaea, Member, honoris causa
- 2019 Israeli Association for Artificial Intelligence, Lifetime Achievement and Service Award

- Martin Charles Golumbic; Clinton F. Goss (Summer 1978). "Perfect Elimination and Chordal Bipartite Graphs".
*Journal of Graph Theory*.**2**(2): 155–163. doi:10.1002/jgt.3190020209. - Robert B. K. Dewar; Martin Charles Golumbic; Clinton F. Goss (August 2013) [First published October 1979].
*MICRO SPITBOL*. Computer Science Department Technical Report. No. 11. Courant Institute of Mathematical Sciences. arXiv: 1308.6096 . Bibcode:2013arXiv1308.6096D.

- Martin Charles Golumbic; Robert B. K. Dewar; Clinton F. Goss (1980). "Macro Substitutions in MICRO SPITBOL - a Combinatorial Analysis".
*Proc. 11th Southeastern Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, Utilitas Math., Winnipeg, Canada*.**29**: 485–495. - Martin Charles Golumbic,
*Algorithmic Graph Theory and Perfect Graphs*, First edition, Academic Press, New York, 1980, Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. - Martin Charles Golumbic, ed.,
*Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems*, Springer-Verlag, New York, 1990. - Martin Charles Golumbic and Ann N. Trenk,
*Tolerance Graphs*, Cambridge University Press, 2004. - Martin Charles Golumbic and Irith B.-A. Hartman, eds.,
*Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications*, Springer-Verlag, New York, 2005. - Martin Charles Golumbic,
*Reasoning about time*, (book chapter in*Mathematical Aspects of Artificial Intelligence*, F. Hoffman, ed., American Math. Society, Proc. Symposia in Applied Math., vol. 55, 1998, pp. 19–53. - Martin Charles Golumbic and Vladimir Gurvich,
*Read-once functions*, (book chapter in*Boolean Functions: Theory, Algorithms and Applications*, Y. Crama and P.L. Hammer, eds., Cambridge University Press, 2011. - Martin Charles Golumbic,
*Fighting Terror Online: The Convergence of Security, Technology, and the Law*, Springer-Verlag, New York, 2008.

**Combinatorics** is a branch of mathematics concerning the study of finite or countable discrete structures.

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.

**SPITBOL** is a compiled implementation of the SNOBOL4 programming language. Originally targeted for the IBM System/360 and System/370 family of computers, it has now been ported to most major microprocessors including the SPARC. It was created by Robert Dewar and Ken Belcher, who were then at the Illinois Institute of Technology.

In graph theory, a **perfect graph** is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. Equivalently stated in symbolic terms an arbitrary graph is perfect if and only if we have:

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, the **complement** or **inverse** of a graph G is a graph H on the same vertices such that two distinct vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and removes all the edges that were previously there. It is not, however, the set complement of the graph; only the edges are complemented.

**Jack R. Edmonds** is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, polyhedral combinatorics, discrete mathematics and the theory of computing. He was the recipient of the 1985 John von Neumann Theory Prize.

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. A prototypical example of this phenomenon is Kuratowski's theorem, which states that a graph is planar if and only if it does not contain either of two forbidden graphs, the complete graph *K*_{5} and the complete bipartite graph *K*_{3,3}. For Kuratowski's theorem, the notion of containment is that of graph homeomorphism, in which a subdivision of one graph appears as a subgraph of the other. Thus, every graph either has a planar drawing or it has a subdivision of one of these two graphs as a subgraph.

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 mathematics, a **permutation graph** is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

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, a **perfectly orderable graph** is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

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.

In graph theory, **trapezoid graphs** are intersection graphs of trapezoids between two horizontal lines. They are a class of co-comparability graphs that contain interval graphs and permutation graphs as subclasses. A graph is a **trapezoid graph** if there exists a set of trapezoids corresponding to the vertices of the graph such that two vertices are joined by an edge if and only if the corresponding trapezoids intersect. Trapezoid graphs were introduced by Dagan, Golumbic, and Pinter in 1988. There exists algorithms for chromatic number, weighted independent set, clique cover, and maximum weighted clique.

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.

In the mathematical area of graph theory, a **chordal bipartite graph** is a bipartite graph *B* = (*X*,*Y*,*E*) in which every cycle of length at least 6 in *B* has a *chord*, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

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.

**Ann Natalie Trenk** is an American mathematician interested in graph theory and the theory of partially ordered sets, and known for her research on proper distinguishing colorings of graphs and on tolerance graphs. She is a professor of mathematics at Wellesley College.

- ↑ Martin Charles Golumbic (1990). "Editorial welcome".
*Annals of Mathematics and Artificial Intelligence*.**1**(1–4): I–III. doi:10.1007/BF01531065. - ↑ Martin Charles Golumbic at the Mathematics Genealogy Project

- Berge, Claude (1963). "Perfect graphs".
*Six Papers on Graph Theory*. Calcutta: Indian Statistical Institute. pp. 1–21. - Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999).
*Graph Classes: A Survey*. SIAM Monographs on Discrete Mathematics and Applications. ISBN 0-89871-432-X. - Erdős, Paul; Goodman, A. W.; Pósa, Louis (1966). "The representation of a graph by set intersections".
*Canadian Journal of Mathematics*.**18**(1): 106–112. doi:10.4153/CJM-1966-014-3. MR 0186575. - Golumbic, Martin Charles (1980). "Algorithmic Graph Theory and Perfect Graphs". Academic Press. ISBN 0-444-51530-5.Cite journal requires
`|journal=`

(help) Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004. - Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995). "Graph sandwich problems".
*J. Algorithms*.**19**(3): 449–473. doi:10.1006/jagm.1995.1047. - Lipshteyn, Marina; Levit, Vadim E.; McConnell, Ross (Eds.) (2009).
*Graph Theory, Computational Intelligence and Thought, Essays Dedicated to Martin Charles Golumbic on the Occasion of His 60th Birthday*. Springer Lecture Notes in Computer Science, Vol. 5420. ISBN 978-3-642-02028-5.CS1 maint: multiple names: authors list (link) CS1 maint: extra text: authors list (link) - Lovász, László (1972). "A characterization of perfect graphs".
*Journal of Combinatorial Theory, Series B*.**13**(2): 95–98. doi:10.1016/0095-8956(72)90045-7. - Lovász, László (1983). "Perfect graphs". In Beineke, Lowell W.; Wilson, Robin J. (eds.).
*Selected Topics in Graph Theory, Vol. 2*. Academic Press. pp. 55–87. ISBN 0-12-086202-6. - McKee, Terry A.; McMorris, F. R. (1999).
*Topics in Intersection Graph Theory*. Philadelphia: Society for Industrial and Applied Mathematics (SIAM Monographs on Discrete Mathematics and Applications, No. 2). ISBN 0-89871-430-3. MR 1672910. - Mahadev, N. V. R.; Peled, Uri N. (1995). "Threshold Graphs and Related Topics". Elsevier.Cite journal requires
`|journal=`

(help) - Szpilrajn-Marczewski, E. (1945). "Sur deux propriétés des classes d'ensembles".
*Fund. Math*.**33**: 303–307. doi:10.4064/fm-33-1-303-307. MR 0015448. - Trotter, William T. (1992).
*Combinatorics and Partially Ordered Sets — Dimension Theory*. Johns Hopkins University Press.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.