The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Cet article examine comment les informations géométriques peuvent être utilisées efficacement pour des algorithmes efficaces en mettant l'accent sur les problèmes de clustering. Étant donné un graphique pondéré complet G of n sommets, existe-t-il une partition du sommet définie dans k des sous-ensembles disjoints afin que le poids maximum d'un bord de cluster interne (dont les deux extrémités appartiennent tous deux au même sous-ensemble) soit minimisé ? Ce problème est connu pour être NP-complet même pour k = 3. Le cas de k=2, c'est-à-dire que le problème de bipartition peut être résolu en temps polynomial. D'un autre côté, dans un contexte géométrique où les sommets sont des points dans le plan et les poids des arêtes sont égaux aux distances entre les points correspondants, le même problème peut être résolu en temps polynomial même pour k
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.
Copier
Tetsuo ASANO, "Effective Use of Geometric Information for Clustering and Related Topics" in IEICE TRANSACTIONS on Information,
vol. E83-D, no. 3, pp. 418-427, March 2000, doi: .
Abstract: This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k
URL: https://global.ieice.org/en_transactions/information/10.1587/e83-d_3_418/_p
Copier
@ARTICLE{e83-d_3_418,
author={Tetsuo ASANO, },
journal={IEICE TRANSACTIONS on Information},
title={Effective Use of Geometric Information for Clustering and Related Topics},
year={2000},
volume={E83-D},
number={3},
pages={418-427},
abstract={This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k
keywords={},
doi={},
ISSN={},
month={March},}
Copier
TY - JOUR
TI - Effective Use of Geometric Information for Clustering and Related Topics
T2 - IEICE TRANSACTIONS on Information
SP - 418
EP - 427
AU - Tetsuo ASANO
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E83-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2000
AB - This paper surveys how geometric information can be effectively used for efficient algorithms with focus on clustering problems. Given a complete weighted graph G of n vertices, is there a partition of the vertex set into k disjoint subsets so that the maximum weight of an innercluster edge (whose two endpoints both belong to the same subset) is minimized? This problem is known to be NP-complete even for k = 3. The case of k=2, that is, bipartition problem is solvable in polynomial time. On the other hand, in geometric setting where vertices are points in the plane and weights of edges equal the distances between corresponding points, the same problem is solvable in polynomial time even for k
ER -