Thumbnail
Access Restriction
Open

Author Everett, Hazel ♦ Klein, Sulamita ♦ Reed, Bruce
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Clique-cross Partition ♦ Optimal Algorithm ♦ Time Algorithm
Abstract We consider the problem of determining whether or not the vertices of a graph can be partitioned into four disjoint cliques A; B; C; D such that vertices of A are not adjacent to vertices of C and vertices of B are not adjacent to vertices of D. We call this a clique-cross partition. We give an O(m + n)-time algorithm to determine if a graph G with n vertices and m edges has such a partition, and give the partition in the case it exists.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study