An efficient parallel algorithm for computing a large independent set in a planar graph |
| |
Authors: | Marek Chrobak and Joseph Naor |
| |
Affiliation: | (1) Department of Mathematics and Computer Science, University of California, 92521 Riverside, CA, USA;(2) Department of Computer Science, Stanford University, 94305-2140 Stanford, CA, USA |
| |
Abstract: | Let (G) denote the independence number of a graphG, that is the maximum number of pairwise independent vertices inG. We present a parallel algorithm that computes in a planar graphG = (V, E), an independent set
such that ¦I¦ (G)/2. The algorithm runs in timeOlog2
n) and requires a linear number of processors. This is achieved by denning a new set of reductions that can be executed locally and simultaneously; furthermore, it is shown that a constant fraction of the vertices in the graph are reducible. This is the best known approximation scheme when the number of processors available is linear; parallel implementation of known sequential algorithms requires many more processors.Joseph Naor was supported by Contract ONR N00014-88-K-0166. Most of this work was done while he was a post-doctoral fellow at the Department of Computer Science, University of Southern California, Los Angeles, CA 90089-0782, USA. |
| |
Keywords: | Planar graphs Independent set Parallel algorithms |
本文献已被 SpringerLink 等数据库收录! |
|