Session 2 Graphs I

9:00 AM-10:40 AM
Room: Mencken
Chair: Derek Corneil, University of Toronto, Canada

9:40-9:17 Max Cut in Toroidal Graphs: Anna Galluccio, Istituto di Analisi dei Sistemi ed Informatica-CNR, Rome, Italy; and Martin Loebl, Charles University, Prague, Czech Republic
9:20-9:37 Efficient Algorithms for Petersen's Matching Theorem: Therese C. Biedl, McGill University, Montréal, Canada; Prosenjit Bose, Carleton University, Ottawa, Canada; Erik D. Demaine and Anna Lubiw University of Waterloo, Canada
9:40-9:57 Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs: Alan M. Frieze and Lei Zhao, Carnegie-Mellon University
10:00-10:17 A Generalization of Janson Inequalities and Its Application to Finding Shortest Paths: C.R. Subramanian, Max-Planck Institute für Informatik, Saarbrücken, Germany
10:20-10:37 Clustering in Large Graphs and Matrices

P. Drineas, Yale University; Alan Frieze, Carnegie Mellon University; R. Kannan, Yale University; V. Vinay, Indian Institute of Science, Bangalore, India, and Yale University; and Santosh Vempala, Massachusetts Institute of Technology

tjf, 9/11/98; MMD, 10/27/98