id: 06057346 dt: a an: 06057346 au: De, Minati; Nandy, Subhas C.; Roy, Sasanka ti: In-place algorithms for computing a largest clique in geometric intersection graphs. so: Snoeyink, Jack (ed.) et al., Frontiers in algorithmics and algorithmic aspects in information and management. Joint international conference, FAW-AAIM 2012, Beijing, China, May 14‒16, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29699-4/pbk). Lecture Notes in Computer Science 7285, 327-338 (2012). py: 2012 pu: Berlin: Springer la: EN cc: ut: ci: li: doi:10.1007/978-3-642-29700-7_30 ab: Summary: In this paper, we study the problem of designing in-place algorithms for finding the maximum clique in the intersection graphs of axis-parallel rectangles and disks in 2D. We first propose $O(n ^{2} \log n)$ time in-place algorithms for finding the maximum clique of the intersection graphs of a set of axis-parallel rectangles of arbitrary sizes. For the rectangle intersection graph of fixed height rectangles, the time complexity can be slightly improved to $O(n \log n + nK)$, where $K$ is the size of the maximum clique. For disk graphs, we consider two variations of the maximum clique problem, namely geometric clique and graphical clique. The time complexity of our algorithm for finding the largest geometric clique is $O(n ^{2} \log n)$, and it works for disks of arbitrary radii. For graphical clique, our proposed algorithm works for unit disks (i.e., of same radii) and the worst case time complexity is $O(n ^{2} + mK ^{4}); m$ is the number of edges in the unit disk intersection graph, and $K$ is the size of the largest clique in that graph. It uses $O(n ^{4})$ time in-place computation of maximum matching in a bipartite graph, which is of independent interest. All these algorithms need $O(1)$ work space in addition to the input array $\cal R$. rv: