Faster Enumeration of All Maximal Cliques in Unit Disk Graphs Using Geometric Structure

Taisuke IZUMI  Daisuke SUZUKI  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E98-D   No.3   pp.490-496
Publication Date: 2015/03/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014FCP0018
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science---New Spirits in Theory of Computation and Algorithm---)
Category: 
Keyword: 
enumerating maximal cliques,  Bron-Kerbosch algorithm,  Unit disk graph,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper considers the problem of enumerating all maximal cliques in unit disk graphs, which is a plausible setting for applications of finding similar data groups. Our primary interest is to develop a faster algorithm using the geometric structure about the metric space where the input unit disk graph is embedded. Assuming that the distance between any two vertices is available, we propose a new algorithm based on two well-known algorithms called Bron-Kerbosch and Tomita-Tanaka-Takahashi. The key idea of our algorithm is to find a good pivot quickly using geometric proximity. We validate the practical impact of our algorithm via experimental evaluations.