Optimal parallel verification of minimum spanning trees in logarithmic time |
| |
| Authors: | B. Dixon R. E. Tarjan |
| |
| Affiliation: | (1) Department of Computer Science, University of Alabama, 35487-0207 Tuscaloosa, AL, USA;(2) Department of Computer Science, Princeton University, 08544 Princeton, NJ, USA;(3) NEC Research Institute, 08540 Princeton, NJ, USA |
| |
| Abstract: | We present the first optimal parallel algorithms for the verification and sensitivity analysis of minimum spanning trees. Our algorithms are deterministic and run inO(logn) time and require linear-work in the CREW PRAM model. These algorithms are used as a subroutine in the linear-work randomized algorithm for finding minimum spanning trees of Cole, Klein, and Tarjan. Research partially supported by a National Science Foundation Graduate Fellowship and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. Research at Princeton University was partially supported by the National Science Foundation, Grant No. CCR-8920505, the Office of Naval Research, Contract No. N00014-91-J-1463, and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center, Grant No. NSF-STC88-09648. |
| |
| Keywords: | Minimum spanning tree Network optimization Verification algorithms Sensitivity analysis |
| 本文献已被 SpringerLink 等数据库收录！ |
|
