A P-complete graph partition problem

DOI10.1016/0304-3975(90)90026-EzbMath0704.68059MaRDI QIDQ917313

R. Sarnath, Xin He

Publication date: 1990

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexityP-complete problemsgraph partition problemlexicographical first different than majority labelling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Depth-first search is inherently sequential
• The maximum flow problem is log space complete for P
• A taxonomy of problems with fast parallel algorithms
• A Simple Parallel Algorithm for the Maximal Independent Set Problem

This page was built for publication: A P-complete graph partition problem