An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem

DOI10.1137/S0097539793260775zbMath0844.68051MaRDI QIDQ4877521

Honghua Yang, Vijaya Ramachandran

Publication date: 18 August 1996

Published in: SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

planar monotone circuit

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Distributed algorithms (68W15)

Related Items (4)

Some Halting Problems for Abelian Sandpiles Are Undecidable in Dimension Three ⋮ A generalization of Spira's theorem and circuits with small segregators or separators ⋮ The Monotone Circuit Value Problem with Bounded Genus Is in NC ⋮ The complexity of the comparator circuit value problem

This page was built for publication: An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem