clarke@utcsri.UUCP (Jim Clarke) (01/13/87)
(SF = Sandford Fleming Building, 10 King's College Road)
(GB = Galbraith Building, 35 St. George Street)
COLLOQUIUM/GRAPHICS, Tuesday, January 20, 11 am, SF1101
Mr. John M. Carroll
IBM Watson Research Center
``Science is Soft at the Frontier"
It is fantastic to imagine that we can start right out on a ``hard"
psychological theory to guide designs for integrated co-authoring applica-
tions on workstations that support multi-media input/output when we can
barely couch such a theory for well-worked, toy domains like cryptarith-
metic and chess. We must of course strive to make our science harder. But
we must also guard against too much weight being given to superficial rigor
and too little to the practical value of our theories in guiding the design
of new technology. I urge that we recognize that in a rapidly evolving,
technology-driven area hard science can never drive out the soft. First,
we must develop an arsenal of realistic empirical methods, methods that
efficiently and reliably produce information at the right level to impact
the application of new technology, not at merely convenient levels.
Second, we must develop qualitative theories, and means for expressing such
theories. Finally, we must extend the scope of our theories.
A.I. SEMINAR, Tuesday, January 20, 3 pm, GB120
Professor Alan Frisch
University of Illinois
Title: To Be Announced
GRAPHICS SEMINAR, Thursday, January 22, 10 am, GB244
Dr. Austin Henderson
Xerox Palo Alto Research Center
``Rooms"
THEORY SEMINAR, Thursday, January 22, 3 pm, GB220
Professor Merrick Furst
Carnegie-Mellon University
Title: To Be Announced
COMBINATORICS SEMINAR, Friday, January 23, 2 pm, GB221
Professor Egon Balas
Carnegie-Mellon University
``Graphs with Polynomially Solvable Maximum-Weight Clique Problem"
The maximum-weight clique problem in a graph G (or, equivalently, the
maximum-weight vertex packing problem in the complement G of G) is notori-
ously hard. However, for certain classes of graphs (e.g. perfect) it is
polynomially solvable. We discuss some new classes with this property and
a general principle that gives rise to them. The principle involves the
existence of a ``clique base", i.e. a polynomial-sized collection of
cliques such that every clique of G is contained in the union of two
cliques of B. We also give a new bound on the number of maximal cliques in
an arbitrary graph, which we use to identify graphs with an appropriate
clique base.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
{allegra,cornell,decvax,linus,utzoo}!utcsri!clarke