The search functionality is under construction.
The search functionality is under construction.

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

Taisuke IZUMI, Daisuke SUZUKI

  • Full Text Views

    0

  • Cite this

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.

Publication
IEICE TRANSACTIONS on Information Vol.E98-D No.3 pp.490-496
Publication Date
2015/03/01
Publicized
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

Authors

Taisuke IZUMI
  Graduate School of Engineering, Nagoya Institute of Technology
Daisuke SUZUKI
  Graduate School of Engineering, Nagoya Institute of Technology

Keyword