Martin Charles Golumbic - Publications#


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


“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.
Imprint Privacy policy « This page (revision-3) was last updated on Monday, 14. October 2013, 16:23 by Kaiser Dana
  • operated by