A P-complete graph partition problem

The Different Than Majority Labelling (DTML) problem has a simple polynomial time sequential algorithm. The labelling given by this algorithm is called the Lexicographical First DTML. In this paper we show that the LF-DTML problem is P-complete. Furthermore, we show that even when restricted to planar graphs, the LF-DTML problem remains P-complete.

Authors

• R. Sarnath
• Xin He

Keywords

No keywords are indexed for this paper.