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

Keyword Search Result

[Keyword] Unit disk graph(1hit)

1-1hit
  • Faster Enumeration of All Maximal Cliques in Unit Disk Graphs Using Geometric Structure

    Taisuke IZUMI  Daisuke SUZUKI  

     
    PAPER

      Vol:
    E98-D No:3
      Page(s):
    490-496

    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.