An Efficient Parallel Algorithm for the Layered Planar Monotone Circuit Value Problem |
| |
Authors: | Vijaya Ramachandran Honghua Yang |
| |
Affiliation: | (1) Department of Computer Sciences, University of Texas at Austin, Austin, TX 78712, USA. vlr@cs.utexas.edu. yanghh@cs.utexas.edu., US |
| |
Abstract: | A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR
gates. A layered PMC is a PMC in which all input nodes are in the external face, and the gates can be assigned to layers in
such a way that every wire goes between gates in successive layers. Goldschlager, Cook and Dymond, and others have developed
NC
2
algorithms to evaluate a layered PMC when the output node is in the same face as the input nodes. These algorithms require
a large number of processors (Ω(n
6
), where n is the size of the input circuit).
In this paper we give an efficient parallel algorithm that evaluates a layered PMC of size n in time using only a linear number of processors on an EREW PRAM. Our parallel algorithm is the best possible to within a polylog
factor, and is a substantial improvement over the earlier algorithms for the problem.
Received April 18, 1994; revised April 7, 1995. |
| |
Keywords: | , Circuit value problem, Planar monotone circuit, Plane graph, Parallel algorithm, EREW PRAM, |
本文献已被 SpringerLink 等数据库收录! |
|