Sunday, January 17

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 UpdatedClustering 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

SODA'99 Home


Program Updates

Author Index




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