DIMACS Princeton Theory Seminar
Title:
A Faster Minimum Spanning Tree Algorithm
Speaker:
- Bernard Chazelle
- Princeton University
Place:
- Room 402, Computer Science Building
- 35 Olden Street
- Princeton University.
Time:
- 12:05 PM (Lunch will be served at 11:45 AM)
- Friday, March 7, 1997
Contact:
- Sanjeev Arora (arora@cs.princeton.edu)
Abstract:
I will discuss a deterministic method for computing
the minimum spanning tree of a connected graph.
The running time is O(m alpha log alpha), where
alpha= alpha(m,n) is an inverse functional
of Ackermann's function, and n (resp. m) is the number
of vertices (resp. edges).
Document last modified on February 27, 1997