New answers tagged


This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.


Looking at the image in the question, I get the impression that $X_L\cup Y_S$ is a minimal vertex cover of the graph $G$. (This is not fully true: If $X$ contains isolated vertices, then those would be part of $X_L$, but not of a minimal vertex cover.) Good, but there can be many vertex covers of a graph, so this does not yet fully characterize that specific ...


Simply pick up any algorithms book out there, they will all take you through these things. What you are describing is essentially the algorithms (and computational complexity) field. The most popular books are Algorithms by Sedgewick and Wayne, which is free for download, the CLRS Introduction to Algorithms, and the epic Art of Computer Programming by ...

Top 50 recent answers are included