Author name cluster

R. Sarnath

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

1 paper

1 author row

TCS Journal 1990 Journal Article

A P-complete graph partition problem

R. Sarnath
Xin He

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.

Details DOI