The Monotone Circuit Value Problem with Bounded Genus Is in NC

DOI10.1007/978-3-319-42634-1_8zbMath1477.68128OpenAlexW2500167267MaRDI QIDQ2817851

Shouwei Li, Christine Markarian, Friedhelm Meyer auf der Heide, Pavel Podlipyan, Faisal N. Abu-Khzam

Publication date: 2 September 2016

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-42634-1_8

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Parameterized complexity, tractability and kernelization (68Q27)

Related Items (2)

Iterated Type Partitions ⋮ On the Parameterized Parallel Complexity and the Vertex Cover Problem

Cites Work

• Unnamed Item
• Unnamed Item
• Upper bounds for monotone planar circuit value and variants
• Improved upper bounds for vertex cover
• An efficient parallel algorithm for planarity
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A taxonomy of problems with fast parallel algorithms
• An Efficient Parallel Biconnectivity Algorithm
• An Efficient Parallel Algorithm for the General Planar Monotone Circuit Value Problem
• Additivity of the genus of a graph

This page was built for publication: The Monotone Circuit Value Problem with Bounded Genus Is in NC