Martin Charles Golumbic - Publications#

BOOKS

“Algorithmic Graph Theory and Perfect Graphs”, Academic Press, New York, 1980.
Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
4378 citations (from Google Scholar)

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

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

“The Zeroth Book of Graph Theory: An Annotated Translation of Les Réseaux (ou Graphes)─André Sainte-Laguë (1926)”, Lecture Notes in Mathematics 2261, Springer, 2021.

EDITED BOOKS

“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, 2005.

“Topics in Algorithmic Graph Theory”, (L. W. Beineki, M. C. Golumbic and R. J. Wilson, eds.), Cambridge University Press, 2021.

SELECTED PAPERS

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

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

“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.

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

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

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

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

Comparability graphs and a new matroid,
J. Comb. Theo. B 22 (1977), 68-90. MR 55 #12575.

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

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

On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses
of chordal graphs, (with B. Ries),
Graphs and Combinatorics 29 (2013), 499-517.

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.

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

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.

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

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

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

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

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.

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

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

Factoring 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-1677.

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

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

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.

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Generalized Fibonacci maximum path graphs, (with Y. Perl),
Discrete Math. 28 (1979), 237-245. MR 81g:05073.

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

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

Why are they called trivially perfect graphs?,
Cadernos do IME - Série Informática 47 (2022), 40-45.

Containment graphs and posets of paths in a tree: wheels and partial wheels, (with V. Limouzy),
Order 38 (2021), 37-48.

The complexity of B1-EPG-Helly graph recognition, (with C. F. Bornstein, T.D. Santos, U. S. Souza and J. L. Szwarcfiter),
Discrete Mathematics and Theoretical Computer Science 22(1)17 (2020), 1-24.

Hardness and approximation for L-EPG and B1-EPG graphs, (with D. Epstein, A. Lahiri and G. Morgenstern),
Discrete Applied Math. 281 (2020), 224-228.

Total coloring of rooted path graphs,
Information Processing Letters 135 (2018), 73-76.

Edge-intersection graphs of boundary-generated paths in a grid, (with G. Morgenstern and D. Rajendraprasad),
Discrete Applied Math. 236 (2018), 214-222.

The induced separation dimension of a graph, (with E. Ziedan, D. Rajendraprasad, R. Mathew and J. Dusart),
Algorithmica 80 (2018), 2834-2848.

Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2, (with E. Cohen, M. Lipshteyn and M. Stern),
Discrete Mathematics 340 (2017), 209-222.

Separation dimension of graphs and hypergraphs, (with M. Basavaraju, L. S. Chandran, R. Mathew and D. Rajendraprasad),
Algorithmica 75 (2016), 187-204.

Posets and VPG graphs, (with E. Cohen, W. T. Trotter and R. Wang),
Order 33 (2016), 39-49.

Characterizations of cographs as intersection graphs of paths on a grid, (with E. Cohen and B. Ries),
Discrete Applied Mathematics 178 (2014), 46-57.

Co-TT graphs and a characterization of split co-TT graphs, (with N. Lefel Weingarten and V. Limouzy),
Discrete Applied Math. 165 (2014), 168–174.

Single bend paths on a grid have strong Helly number 4, (with M. Lipshteyn and M. Stern),
Networks 62 (2013), 161-163.

On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, (with B. Ries),
Graphs and Combinatorics 29 (2013), 499-517.

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.

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