DIMACS TR: 94-56
A Linear-time Algorithm for Network Decomposition
Author: Lenore J. Cowen
ABSTRACT
An algorithm for low-diameter network decomposition on arbitrary
graphs is presented which runs in O(E + n) time. Previous algorithms
ran in O(E log n + n) time.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-56.ps
DIMACS Home Page