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.
Taisuke IZUMI
Graduate School of Engineering, Nagoya Institute of Technology
Daisuke SUZUKI
Graduate School of Engineering, Nagoya Institute of Technology
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copy
Taisuke IZUMI, Daisuke SUZUKI, "Faster Enumeration of All Maximal Cliques in Unit Disk Graphs Using Geometric Structure" in IEICE TRANSACTIONS on Information,
vol. E98-D, no. 3, pp. 490-496, March 2015, doi: 10.1587/transinf.2014FCP0018.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2014FCP0018/_p
Copy
@ARTICLE{e98-d_3_490,
author={Taisuke IZUMI, Daisuke SUZUKI, },
journal={IEICE TRANSACTIONS on Information},
title={Faster Enumeration of All Maximal Cliques in Unit Disk Graphs Using Geometric Structure},
year={2015},
volume={E98-D},
number={3},
pages={490-496},
abstract={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.},
keywords={},
doi={10.1587/transinf.2014FCP0018},
ISSN={1745-1361},
month={March},}
Copy
TY - JOUR
TI - Faster Enumeration of All Maximal Cliques in Unit Disk Graphs Using Geometric Structure
T2 - IEICE TRANSACTIONS on Information
SP - 490
EP - 496
AU - Taisuke IZUMI
AU - Daisuke SUZUKI
PY - 2015
DO - 10.1587/transinf.2014FCP0018
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E98-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2015
AB - 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.
ER -