LOW-DIAMETER GRAPH DECOMPOSITION IS IN NC

Authors
AWERBUCH B BERGER B COWEN L PELEG D
Citation
B. Awerbuch et al., LOW-DIAMETER GRAPH DECOMPOSITION IS IN NC, Random structures & algorithms, 5(3), 1994, pp. 441-452
Citations number
15
Categorie Soggetti
Mathematics,Mathematics,Mathematics,"Computer Science Software Graphycs Programming
Journal title
Random structures & algorithms → ACNP
ISSN journal
10429832
Volume
5
Issue
3
Year of publication
1994
Pages
441 - 452
Database
ISI
SICI code
1042-9832(1994)5:3<441:LGDIIN>2.0.ZU;2-D
Abstract
We obtain the first NC algorithm for the low-diameter graph decomposit ion problem on arbitrary graphs. Our algorithm runs in O(log5(n)) time , and uses O(n2) processors. (C) 1994 John Wiley & Sons, Inc.