4.1 Introductory discussion
We shortly recall the O(n3 + out) algorithm from [9]. In this algorithm, it has been shown that each maximal clique is uniquely described by the 3 parameters t, h and v denoting the hypotenuse t of the lowest semi-square, the highest base h of any semi-square and the rightmost vertical side v. The drawback of the algorithm given in [9] is that it needs O(n3) time even if there are only very few maximal cliques. In the case of c-max-tolerance graphs we can now present a considerably improved output-sensitive algorithm.
Our description consists of two steps: First we will give an algorithm that computes all candidates for maximal cliques with one fixed parameter, say a given lowest hypotenuse t. We show that all maximal cliques with fixed parameter t can be determined in time O(n log n + out) where out is the size of the output.
The problem is, however, that these maximal cliques could still be extendable by a semi-square with an even lower hypotenuse t'. Thus, such a maximal clique with fixed parameter t is only a candidate that has to be checked for extensibility before printing it out. In the second step, we will show how to avoid the computation of candidates that do not represent maximal cliques such that our final algorithm will truly be output-sensitive.