Martin Charles Golumbic

 

BOOKS

  •  “Algorithmic Graph Theory and Perfect Graphs”,  
            Academic Press, New York, 1980. Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.  

  • “Tolerance Graphs”, (with Ann N. Trenk),
            Cambridge University Press, 2004.

 

EDITED BOOK

  • Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems”,  (M. C. Golumbic, ed.), Springer-Verlag, New York, 1990. 

  • “Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications”, (M. C. Golumbic and I.B.-A. Hartman, eds.), Springer-Verlag, New York, 2004. 

 

BOOK CHAPTERS

  • “Reasoning about time”, in “Mathematical Aspects of Artificial Intelligence”, F. Hoffman, ed.,  American Math. Society, Proc. Symposia in Applied Math., vol. 55, 1998, pp. 19-53.

  • “Read-once functions”, (with V. Gurvich),  in  “Boolean Functions: Theory, Algorithms and Applications”, Y. Crama and P.L. Hammer, eds., Cambridge University Press, 2009.

  • “Perspectives on Reasoning about Time”, in “Ubiquitous Display Environments” , A. Krüger and T. Kuflik, eds.,Springer Verlag, to appear 2012.

 

EDITED JOURNAL SPECIAL ISSUES

  • “Artificial Intelligence and Mathematics”, (M.C. Golumbic, et al., eds.),  volumes 5(2-4), 6(4), 15(1), 17(3-4), 23(3-4), 24, 26, 28, 33(1), 36(4), 38(4), 39(4), 42(4), 45(3-4), 46(4), 48(1-2), 51(1), 52(1), 55(3-4), 57(2), 57(3-4), 59(1), 60(3-4), 61(1), 63(2) J.C. Baltzer AG, Basel, 1992, 1995, 1996, 1998. Kluwer Academic Publishers, 2000-2004. Springer, 2005-2011.

  • “Foundations of Artificial Intelligence”, (M.C. Golumbic, et al., eds.), Annals of Mathematics and Artificial Intelligence 4 (3-4), 9 (3-4), 20 (1-4), J.C. Baltzer AG, Basel, 1991, 1993, 1997.

  • “In Memory of Martin Farber”, (M. C. Golumbic and R. Laskar, eds.) Discrete Applied Mathematics, volume 44, North-Holland, Amsterdam, 1993.  

  • “Combinatorics and Algorithms”, (N. Alon, A.S. Fraenkel, M. C. Golumbic, E. Shamir, eds.)  Discrete Mathematics, volume 114, North-Holland, Amsterdam, 1993.  

  • “Horn Logic, Search and Satisfiability”, (M.C. Golumbic, P.L. Hammer, P. Hansen and T. Ibaraki, eds.), Annals of Mathematics and Artificial Intelligence, volume 1, J.C. Baltzer AG, Basel, 1990.

  • “Approaches to Intelligent Decision Support”, (R. Jeroslow, E. Barrett, M.C. Golumbic,H. Greenberg, F. Leimkuhler, W. Marek, F.Tonge, T. Morton, A. Whinston, eds.), Annals of Operations Research, volume 12, J.C. Baltzer AG, Basel, 1988.

  • “Interval Graphs and Related Topics”, (M. C. Golumbic, ed.), Discrete Mathematics, volume 55, number 2, North-Holland, Amsterdam, 1985.

EDITED PROCEED

  • “Proceedings of the Fourth Bar-Ilan Symposium on Foundations of Artificial Intelligence”, (M. Koppel, E. Shamir and M. Golumbic, eds.), AAAI Press, 1995. ISBN 978-1-57735-011-8

 

OTHER BOOKS

  • “Fighting Terror Online: The Convergence of Security, Technology, and the Law”, Springer-Verlag, New York, 2008.

 

PAPERS IN REFEREED JOURNALS

J62. On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, (with B. Ries), Graphs and Combinatorics (to appear 2012).

J61. Intersection graphs of paths on a grid,(with A. Asinowski, E. Cohen, V. Limouzy, M. Lipshteyn and M. Stern), Journal of Graph Algorithms and Applications 16 (2012) 129-150.

J60. Path-bicolorable graphs, (with A. Brandstadt, Van Bang Le, and M. Lipshteyn), Graphs and Combinatorics 27 (2011), 799-819.

J59. The chain graph sandwich problem,(with S. Dantas, C.M.H. de Figueiredo, S. Klein, F. Maffray), Annals of Operations Research 188 (2011), 133-139.

J58. On the bi-enhancement of chordal-bipartite probe graphs, (with E. Cohen, M. Lipshteyn and M. Stern), Inform. Proc. Letters 110 (2010), 193-197.

J57. A characterization of chain probe graphs, (with F. Maffray and G. Morel), Annals of Operations Research 188 (2011), 175-183.

J56. Intersection models of weakly chordal graphs, (with M. Lipshteyn and M. Stern), Discrete Applied Math. 157 (2009), 2031-2047.

J55. Edge intersection graphs of single bend paths on a grid, (with M. Lipshteyn and M. Stern), Networks 54 (2009), 130-138.

J54. Equivalences and the complete hierarchy of intersection graphs of paths in a tree,(with M. Lipshteyn and M. Stern), Discrete Applied Math. 156 (2008), 3203-3215.

J53. An improvement on the complexity of factoring read-once Boolean functions, (with A. Mintz and U. Rotics), Discrete Applied Math. 156 (2008), 1633-1636.

J52. Representing edge intersection graphs of paths on degree 4 trees, (with M. Lipshteyn and M. Stern), Discrete Mathematics 308 (2008), 1381-1387.

J51. The k-edge intersection graphs of paths in a tree, (with M. Lipshteyn and M. Stern), Discrete Applied Math. 156 (2008), 451-461.

J50. Recognizing chordal probe graphs and cycle-bicolorable graphs, (with A. Berry and M. Lipshteyn), SIAM J. Discrete Math 21 (2007) 573-591.

J49. FacFactoring and recognition of read-once functions using cographs and normality and the readability of functions associated with partial k-trees, (with A. Mintz and U. Rotics), Discrete Applied Math. 154 (2006), 1465-1477.

J48. Rank tolerance graph classes, (with R. E. Jamison), J. of Graph Theory 52 (2006) 317-340.

J47. Factoring Boolean functions using graph partitioning, (with A. Mintz), Discrete Applied Math. 149 (2005), 131-153.

J46. On the complexity of cell flipping problems in permutation diagrams,and multiprocessor scheduling problems (with H. Kaplan and E. Verbin), Discrete Math., 296 (2005), 25-41.

J45. Chordal probe graphs, (with M. Lipshteyn), Discrete Applied Math. 143 (2004), 221-237.

J44. Archimedian Φ-tolerance graphs, (with R.E. Jamison and A.N. Trenk), J. of Graph Theory 41 (2002), 179-194.

J43. Block duplicate graphs and a hierarchy of chordal graphs, (with U. Peled), Discrete Applied Math. 124 (2002), 67-71.

J42. On the number of vertices belonging to all maximal stable sets of a graph, (with E. Boros and V.E. Levit), Discrete Applied Math. 124 (2002), 17-25.

J41. Uniquely restricted matchings in graphs, (with T. Hirst and M. Lewenstein), Algorithmica 31 (2001), 139-154.

J40. On the clique-width of some perfect graph classes, (with U. Rotics), International Journal of Foundations of Computer Science 11 (2000), 423-443.

J39. New results on induced matchings, (with M. Lewenstein), Discrete Applied Math. 101 (2000), 157-165.

J38. Matrix sandwich problems, Linear Algebra and Appl. 277 (1998), 239-251.

J37. Complexity and algorithms for graph and hypergraph sandwich problems, (with A. Wassermann), Graphs and Combinatorics 14 (1998), 223-239.

J36. Graph sandwich problems, (with H. Kaplan and R. Shamir), J. of Algorithms 19 (1995), 449-473.

J35. Four strikes against physical mapping of DNA, (with P.W. Goldberg, H. Kaplan and R. Shamir), J.of Comput. Biology 2 (1995), 139-152.

J34. On the complexity of DNA physical mapping, (with H. Kaplan and R. Shamir), Advances in Applied Mathematics 15 (1994), 251-261.

J33. Instruction scheduling across control flow, (with V. Rainish), Scientific Programming 2 (1993), 1-5.

J32. Complexity and algorithms for reasoning about time: a graph-theoretic approach, (with R. Shamir), J. Assoc. Comput. Mach. 40 (1993), 1108-1133.

J31. Optimal program linkage by graph partitioning, with T.K. Philips, R.L. Harvell and K. Lynne) CSI Journal on Computer Science and Informatics (1994).

J30. Counting endpoint sequences for interval orders and interval graphs, (with A. Belfer), Discrete Math. 114 (1993), 23-39.

J29. Irredundancy in circular arc graphs, (with R. Laskar), Discrete Applied Math. 44 (1993), 79-89.

J28. A knowledge representation language for university requirements, (with M. Markovich and M. Tiomkin), Decision Support Systems 7 (1991), 33-45.

J27. Interactive scheduling as a constraint satisfiability problem, (with R. Feldman), Ann. Math. and Artif. Intell. 1 (1990), 49-73.

J26. Optimization algorithms for student scheduling via constraint satisfiability, (with R. Feldman), The Computer Journal 33 (1990), 356-364.

J25. Instruction scheduling beyond basic blocks, (with V. Rainish) IBM J. Res. & Dev. 34 (1990), 93-97.

J24. Containment graphs, posets and related classes of graphs, (with E.R. Scheinerman),  Ann. N.Y. Acad. Sci. 555 (1989), 192-204.

J23. Trapezoid graphs and their coloring, (with I. Dagan and R.Y. Pinter), Discrete Applied Math. 21 (1988), 35-46.

J22. Stability in circular arc graphs, (with P.L. Hammer), J. of Algorithms 9 (1988), 314-320. 

J21. Algorithmic aspects of intersection graphs and representation hypergraphs, Graphs and Combinatorics 4 (1988), 307-321.

J20. A general method for avoiding cycling in a network,  Inform. Proc. Letters 24 (1987), 251-253.

J19. A knowledge-based expert system for student advising, (with M. Markovich, U.N. Schild and S. Tsur), IEEE Trans. on Education E-28 (1986), 120-124.

J18. Interval graphs and related topics, Discrete Math. 55 (1985), 113-121.

J17.  Edge and vertex intersection of paths in a tree, (with R.E. Jamison), Discrete Math. 55 (1985), 151-159.

J16. The edge intersection graphs of paths in a tree, (with R.E. Jamison), J. Combin. Theory B 38 (1985), 8-22.

J15. Tolerance graphs, (with C.L. Monma and W.T. Trotter, Jr.),  Discrete Applied Math. 9 (1984), 157-170.

J14. Recent results on the strong perfect graph conjecture, (with M.A. Buckingham), Ann. Discrete Math. 20 (1984), 75-82. 

J13. Algorithmic aspects of perfect graphs, Ann. Discrete Math. 21 (1984), 301-323.

J12. Partitionable graphs, circle graphs, and the Berge strong perfect graph conjecture,  (with M.A. Buckingham),  Discrete Math. 44 (1983), 45-54.

J11. Comparability graphs and intersection graphs, (with D. Rotem and J. Urrutia), Discrete Math. 43 (1983), 37-46.

J10. The edge inducibility of graphs, (with Y. Perl), Math. Acad. Sci. Hung. 35 (3-4) (1980), 393-398.

J9. Dirac's theorem on triangulated graphs, Ann. New York Acad. Sci. 319 (1979), 242-246.

J8. Generalized Fibonacci maximum path graphs, (with Y. Perl), Discrete Math. 28 (1979), 237-245.

J7. Trivially perfect graphs, Discrete Math. 24 (1978), 105-107.

J6. Perfect elimination and chordal bipartite graphs, (with C.F. Goss),   J. Graph Theory 2 (1978), 155-163.

J5. A note on perfect Gaussian elimination, J. Math. Anal. Appl. 64 (1978), 455-457.

J4. The complexity of comparability graph recognition and coloring,  Computing 18 (1977), 199-208.

J3. Comparability graphs and a new matroid, J. Comb. Theo. B 22 (1977), 68-90.

J2. Combinatorial merging, IEEE Trans. on Comput. 25 (1976), 1164-1167.

J1. The inducibility of graphs, (with N. Pippenger), J. Comb. Theo. B 19 (1975), 189-203.

 

PAPERS IN REFEREED PROCEEDINGS

( * indicates extended abstract of a paper published later as a journal paper.)

P32. String graphs of k-bend paths on a grid,(with A. Asinowski, E. Cohen, V. Limouzy, M. Lipshteyn and M. Stern), Proc. LAGOS-2011. Electronic Notes in Discrete Mathematics 37 (2011) 141–146..

P31. Smallest Odd Holes in Claw-Free Graphs (Extended Abstract), (with S. Shrem and M. Stern), Proc. 35th Int'l. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2009), Lecture Notes in Computer Science 5911, Springer-Verlag, 2009, pp. 329-340..

P30. *Path-bicolorable graphs, (with A. Brandstadt, V.B. Le, and M. Lipshteyn), Lecture Notes in Computer Science 5420, Springer-Verlag, 2009, pp. 172-182..

P29. *On the bi-enhancement of chordal-bipartite probe graphs, (with E. Cohen, M. Lipshteyn and M. Stern), Proc. Seventh Cologne Twente Workshop on Graphs and Combinatorics (CTW2008), pp.152-156..

P28. What is between chordal and weakly chordal graphs? (with E. Cohen, M. Lipshteyn and M. Stern), Proc. 34rd Int'l. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2008), Lecture Notes in Computer Science 5344, Springer-Verlag, 2008, pp. 275-286..

P27. *Finding intersection models of weakly chordal graphs, (with M. Lipshteyn and M. Stern),Proc. 32nd Int'l. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2006), Lecture Notes in Computer Science 4271, Springer-Verlag, 2006, pp. 241-255.

P26. *Read-once functions revisited and the readability number of a Boolean function, with A. Mintz and U. Rotics),  Electronic Notes in Discrete Mathematics 22 (15 October 2005), pp. 357-361.

P25. *Representations of edge intersection graphs of paths in a tree, (with M. Lipshteyn and M. Stern), Proc. European Conference on Combinatorics, Graph Theory and Applications --Eurocomb 2005,(Berlin, Sept. 2005), Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings volume AE (2005), 87-92.  

P24. Graph theoretic models for reasoning about time, Lecture Notes in Computer Science 3321, Springer-Verlag, 2004, pp. 362-372.

P23. The recognition of k-EPT graphs, (with M. Lipshteyn and M. Stern).Proc. 35th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium 171 (2004), 129-139.

P22. *Two tricks to triangulate chordal probe graphs, (with A. Berry and M. Lipshteyn), Proc. 15th ACM-SIAM Symposium on Discrete Algorithms, SODA-2004, (Jan. 2004), pp. 962-969.

P21. *Chordal probe graphs (extended abstract), (with M. Lipshteyn), Proc. 29th Int'l. Workshop on Graph-Theoretic Concepts in Computer Science (WG 2003), Lecture Notes in Computer Science 2880, Springer-Verlag, 2003, pp. 249-260.

P20. Coloring algorithms for tolerance graphs: reasoning and scheduling with interval constraints (with Assaf Siani),Lecture Notes in Computer Science 2385, Springer-Verlag, 2002, pp. 196-207.

P19. *Factoring and recognition of read-once functions using cographs and normality, (with A. Mintz and U. Rotics), Proc. 38th ACM Design Automation Conference - DAC-2001, (June 2001), pp. 109-104.

P18. On the hierarchy of interval, probe and tolerance graphs, (with M. Lipshteyn),Proc. 32th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium 153, Utilitas Math., Winnipeg, Canada, 2001, pp. 97-106.

P17. *Factoring logic functions using graph partitioning, (with A. Mintz),Proc. 1999 IEEE/ACM Int'l Conf. on Computer-Aided Design - ICCAD-99, (November 1999), IEEE Press, pp. 195-198.

P16. *On the clique-width of perfect graph classes, Extended abstract, (with U. Rotics), Proc. 25th Int'l. Workshop on Graph-Theoretic Concepts in Computer Science (WG 1999), Lecture Notes in Computer Science 1665, Springer-Verlag, 1999, pp. 135-147.

P15. The clique-width of interval graphs is unbounded, (with U. Rotics), Proc. 30th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium 140, Utilitas Math., Winnipeg, Canada, 1999, pp. 5-17.

P14. *Cell flipping in permutation diagrams, (with H. Kaplan), Lecture Notes in Computer Science 1373, Springer-Verlag, 1998, pp. 577-586.

P13. Reasoning about time, (invited 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.

P12. *Algorithms and complexity of sandwich problems in graphs, (with H. Kaplan and R. Shamir), Lecture Notes in Computer Science 790, Springer-Verlag, 1994, pp. 57-69.

P11. *Algorithms and complexity for reasoning about time, (with R. Shamir), Proc. Tenth National Conf. on Artificial Intelligence - AAAI-92, (July 1992), AAAI Press, 1992, pp. 741-747.

P10. *Interval graphs, interval orders and the consistency of temporal events, (with R. Shamir), Lecture Notes in Computer Science 601, Springer-Verlag, 1992, pp. 32-42.

P9. A combinatorial approach to temporal reasoning, (with A. Belfer),Proc. Fifth Jerusalem Conference on Information Technology, IEEE Computer Society Press, October 1990, pp. 774-780.

P8. Learning from experience in board games, (with Z. Ben-Porat), in “Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems”, Springer-Verlag, New York, 1990, pp. 1-25.

P7. Spill code minimization techniques for optimizing compilers, (with D. Bernstein, D.Q. Goldin, H. Krawczyk, Y. Mansour, I. Nahshon, R.Y. Pinter), Proc. ACM SIGPLAN'89 Conference on Programming Language Design and Implementation, (June 1989), 258-263.

P6. *Constraint satisfiability algorithms for interactive student scheduling, (with R. Feldman), Proc. Eleventh Int'l. Joint Conf. on Artificial Intelligence - IJCAI-89 (August 1989), pp. 1010-1016.

P5. A generalization of interval graphs with tolerances, (with C.L. Monma), Proc. 13th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium 35, Utilitas Math., Winnipeg, Canada, 1982, pp. 321-331.

P4. Macro substitutions in MICRO SPITBOL - a combinatorial analysis,(with C.F. Goss and R.B.K. Dewar), Proc. 11th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium 29, Utilitas Math., Winnipeg, Canada, 1980, pp. 485-495.

P3. The inducibility of hypergraphs, Proc. 9th Southeastern Conf. on Combinatorics, Graph Theory and Computing, Congressus Numerantium 21, Utilitas Math., Winnipeg, Canada, 1978, pp. 323-327.

P2. Threshold graphs and synchronizing parallel processes, in “Combinatorics” (A. Hajnal and V. T. Sos, eds.), Colloq. Math. Soc. Janos Bolyai 18 (1978), 419-428. MR 81e:68080.

P1. *Comparability graphs and a new matroid, extended abstract, Proc. Conf. Algebraic Aspects of Combinatorics, Univ. of Toronto, Congressus Numerantium 13, Utilitas Math., Winnipeg, Canada, 1975, pp. 213-217.

 

PAPERS IN UNREFEREED PROCEEDINGS AND SELECTED REPORTS CITED IN THE LITERATURE

 ( ** indicates early version of a paper subsumed later by a published journal paper.)

R12. Chain graphs have unbounded readability, (with U. Peled and U. Rotics), UIC Technical Report, arXiv:math/0610456v1, Oct. 2006.

R11. Algorithmic graph theory and its applications, (book chapter),in “Graph Theory, Combinatorics and Algorithms: Interdisciplinary Applications”, Springer-Verlag, New York, 2005.

R10. Future directions on tolerance graphs, Proc. 30th Southeastern Conf. on Combinatorics, Graph Theory and Computing,Congressus Numerantium 139, Utilitas Math., Winnipeg, Canada, 1999, 213-220.

R9. From data to knowledge-bases, (with D. Grinberg), in “Advances in Artificial Intelligence, Natural Language and Knowledge-based Systems”, Springer-Verlag, New York, 1990, pp. 269-294.

R8. Merging object-oriented programming and logic programming:Implementation and enhancement of the SPOOL language, (with M. Shindler), IBM Israel Technical Report 88.275, August 1989.

R7. Register allocation for TR-Pascal: Preserving a source level debugging environment, (with A. Azagury and H. Krawczyk), IBM Israel Technical Report 88.270, June 1989.

R6. Knowledge-based techniques in an academic environment, Proc. Int'l. Conf. on Courseware and Design and Evaluation, Symposium on Artificial Intelligence and Education, Ramat Gan, Israel, April 1986, pp. 355-362.

R5. **The academic planning environment (APE) expert system, (with S. Tsur and U.N.Schild) Proc. IBM ITL Meeting on Expert Systems, Yorktown Heights, N.Y., October 1984.

R4. **Containment graphs and intersection graphs, NATO Advanced Institute on Ordered Sets, Banff, Canada, May 1984.

R3. A remark on the NP-completeness of the threshold dimension problem, Bell Laboratories Technical Memorandum, 1982.

R2. An infinite class of superperfect noncomparability graphs, IBM Research Report RC 5064, 1974.

R1. The general gossip problem, IBM Research Report RC 4977, 1974.

 

PAPERS IN PREPARATION OR SUBMITTED

S5. Co-TT graphs and a characterization of split co-TT graphs, (with N. Lefel Weingarten and V. Limouzy), submitted.

S4. Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2, (with E. Cohen, M. Lipshteyn and M. Stern), submitted.

S4. Single bend paths on a grid have strong Helly number 4, (with M. Lipshteyn and M. Stern), in preparation.

S2. An effective upperbound on treewidth using partial fill-in of separators, (with B. Faltings), submitted.

S1. Detecting a smallest odd hole in a claw-free graph, (with S. Shrem and M. Stern), submitted.