Alphabetical List‎ > ‎S‎ > ‎

Jayme Luiz Szwarcfiter

Jayme Luiz Szwarcfiter, Jewish Brazilian mathematician and computer scientist (Rio de Janeiro 05 July 1942 –

With D.E. Knuth proposed a structured program to generate all topological sorting arrangements known as Knuth-Szwarcfiter sorting algorithm (1974)

With A. Itai & C. Papadimitriou proved the problem of determining whether or not an instance (G,s, t) of a Hamilton path problem has a solution is NP-complete (1982)

Showed that the general problem of optimizing the cost of a tree, given the keys, the probabilities and the page limit is NP-hard (1984)

Developed polynomial algorithm for recognizing, finding isomorphism between and finding minimum equivalent directed graphs for tree reducible graphs (1985)

Introduced the class of connectively reducible digraphs (1989)   

With C.E. Bornstein characterized the clique graphs of chordal graphs and the clique graphs of path graphs (1994)

With G. Chaty gave an algorithm for generating all distinct kernels in a directed graph D with no odd directed circuits (1994)

Introduced the concept of local comparability graphs and showed that every local comparability graph is a difference of two comparability graphs (1995)

Described a characterization of clique-Helly graphs leading to a polynomial time algorithm for recognizing them (1997)

With C.L. Lucchesi & C.P. de Mello described the family of minimal graphs which are clique-complete but have no universal vertices (1998)

With F. Protti & F. França presented a parallel algorithm for generating all maximal cliques of a graph (1997)

With E. Caceres & S. Song invented a new technique, the unrestricted depth search and presented a parallel algorithm for finding the maximal cliques of a circle graph using the Coarse grained multicomputer model (2001)

With M.R. Cerioli showed that the class of starlike graphs contains the class of edge clique graphs of generalized starlike graphs and every starlike graph which is an edge clique graph is an edge clique graph of a generalized starlike graph (2002) 

With M.R. Cerioli proved that a starlike threshold graph is an edge clique graph if and only if its maximal cliques and intersections of maximal cliques are triangular sets (2002)

With M. Moscarini & R. Petreschi described necessary and sufficient conditions for finding the node-search number of a uniform K-starlike graph

With P.E. Lauer developed an algorithm for enumerating all the directed circuits of a directed graph on edges, vertices and directed circuits

With D. Artigas, S. Dantas e M.C. Dourado developed a linear-time algorithm to decide if a cograph is p-convert (2011)

With C.C. Centeno, M.C. Dourado et al. described a general reduction principle for irrf(G) 2012