An optimal parallel algorithm for planar cycle separators |
| |
Authors: | Ming-Yang Kao Shang-Hua Teng K. Toyama |
| |
Affiliation: | (1) Department of Computer Science, Duke University, 27708 Durham, NC, USA;(2) Department of Mathematics, Massachusetts Institute of Technology, 02139 Cambridge, MA, USA;(3) Department of Computer Science, Yale University, 06520 New Haven, CT, USA |
| |
Abstract: | We present an optimal parallel algorithm for computing a cycle separator of ann-vertex embedded planar undirected graph inO(logn) time onn/logn processors. As a consequence, we also obtain an improved parallel algorithm for constructing a depth-first search tree rooted at any given vertex in a connected planar undirected graph in O(log2n) time on n/logn processors. The best previous algorithms for computing depth-first search trees and cycle separators achieved the same time complexities, but withn processors. Our algorithms run on a parallel random access machine that permits concurrent reads and concurrent writes in its shared memory and allows an arbitrary processor to succeed in case of a write conflict.A preliminary version of this paper appeared as Improved Parallel Depth-First Search in Undirected Planar Graphs in theProceedings of the Third Workshop on Algorithms and Data Structures, 1993, pp. 407–420.Supported in part by NSF Grant CCR-9101385. |
| |
Keywords: | Cycle separators Depth-first search Planar graphs Parallel algorithms |
本文献已被 SpringerLink 等数据库收录! |
|