Journal
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS
Volume E98D, Issue 3, Pages 490-496Publisher
IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG
DOI: 10.1587/transinf.2014FCP0018
Keywords
enumerating maximal cliques; Bron-Kerbosch algorithm; Unit disk graph
Funding
- KAKENHI [25106507, 25289114]
- Inamori Foundation
- Grants-in-Aid for Scientific Research [25106507] Funding Source: KAKEN
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available