NC algorithm for evaluating monotone planar circuits

A. L. Delcher, S. Rao Kosaraju

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


Goldschlager first established that a special case of the monotone planar circuit problem can be solved by a Turing machine in O(log2n) space. Subsequently, Dymond and Cook refined the argument and proved that the same class can be evaluated in O(log2n) time with a polynomial number of processors. In this paper, we prove that the general monotone planar circuit value problem can be evaluated in O(log4n) time with a polynomial number of processors, settling an open problem posed by Goldschlager and Parberry.

Original languageEnglish (US)
Pages (from-to)369-375
Number of pages7
JournalSIAM Journal on Computing
Issue number2
StatePublished - Jan 1 1995

ASJC Scopus subject areas

  • General Computer Science
  • General Mathematics


Dive into the research topics of 'NC algorithm for evaluating monotone planar circuits'. Together they form a unique fingerprint.

Cite this