Professor
Bonnie Berger
| Abstract |
      
|
|
Low Diameter Graph Decomposition is in NC |
| Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg |
|
We obtain the first NC algorithm for the low-diameter graph decomposition problem on arbitrary graphs. Our algorithm runs in O(log5(n)) time, and uses O(n2) processors. |
| http://www.cs.tufts.edu/~cowen/nc.ps |