phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (11/10/83)
UofT Department of Computer Science Seminar Schedule for
the week of November 14th, 1983
Monday, November 14th, 11:00 A.M., GB405: Dr. Kathie Cameron,
University of Maryland, College park, Maryland: "An extension
of the perfect graph theorem".
ABSTRACT: A graph G=(V,E) is called PERFECT if for all A a
subset of V, the maximum size of an independent set in G of A,
the subgraph of G induced by A, equals the minimum size of
a cover of G of A by cliques.
THEOREM: Let the edges of a complete graph be colored red, blue,
and yellow such that no triangle gets all three colors. Suppose
that the graphs formed by the red edges and the blue edges,
respectively, are perfect. Then so is the graph formed by the
yellow edges. Where there are no blue edges this result becomes
the perfect graph theorem.
Joint work with Jack Edmonds and Laszlo Lovasz.
Tuesday, November 15th, 11:00 A.M., GB244: Dr. David D. Clark,
Laboratory for Computer Science, MIT, Cambridge, Mass.: "The
SWIFT Operating System".
ABSTRACT: This talk will describe a new operating system under
development at the Laboratory for Computer Science at MIT. The
goal of this system is to provide a proper environment for
development of such programs as network protocols and window
management packages, which do not seem to to sit well in most
existing systems.
The design for this system is based on an experience with design
and implementation of network protocols. The first part of the
talk will discuss why protocol implementation seemed to fit poorly
into existing operating systems.
The second part of the talk will discuss SWIFT itself. SWIFT has a
number of novel features:
- The use of a type-safe language (CLU) to increase
system reliability.
- The use of garbage collection as an OS storage management
technique.
- A real-time scheduler to support I/O programming.
- Monitors and shared memory for interprocess co-ordination.
The talk will discuss the motivation behind the structure of SWIFT, and
the degree of success that the project has had so far.
Thursday, November 17th, 2:00 P.M., GB24?: Mr. Paliath Narendran, Rensselear
Polytechnic Institute, Department of Mathematics, Troy, New York:
"Church-Rosser and related Thue systems".
Thursday, November 17th, 3:00 P.M., GB 248: Professor Joseph Liu,
York University, Department of Computer Science, Downsview, Ontario:
"Sparse orthogonal decomposition by row merging".
ABSTRACT: General row merging schemes for the orthogonal decomposition
of sparse matrices are examined. They can be viewed as special
variable row pivoting methods, first described by Gentleman in 1975.
Based on the structure of the given sparse matrix, an algorithm is
presented to determine automatically the sequence of row pairs to
be merged. The actual numerical computation for such a row merging
sequence can be organized as a sequence of reductions of two upper
trapezoidal full submatrices into another upper trapezoidal full
matrix. Numerical experiments show that the recent scheme by
George and Heath (1980) require more than three times the amount of
computation used by this scheme.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllis