Martin Charles Golumbic

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.[citation needed]


Golumbic was born in 1948 in Erie, Pennsylvania, U.S.A.. He received his Ph.D. in 1975 at Columbia University where his advisor was the eminent mathematician Samuel Eilenberg. 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. 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 and Rutgers University.

Golumbic is currently the Founder and Director of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science at the University of Haifa. He was elected a Fellow of the Institute of Combinatorics and its Applications (1995), Fellow of the European Coordinating Committee for Artificial Intelligence ECCAI (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 N. Trenk) and Fighting Terror Online: The Convergence of Security, Technology, and the Law.

Scientific Contributions[edit]

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 (EPT), 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.

Honors and awards[edit]


  • 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.6096free to read. 
  • 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.


  • 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.  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. 
  • 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. 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. 
  • Szpilrajn-Marczewski, E. (1945). "Sur deux propriétés des classes d'ensembles". Fund. Math. 33: 303–307. MR 0015448. 
  • Trotter, William T. (1992). Combinatorics and Partially Ordered Sets — Dimension Theory. Johns Hopkins University Press. 

External links[edit]