La fonctionnalité de recherche est en construction.
La fonctionnalité de recherche est en construction.

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

Effective Use of Geometric Information for Clustering and Related Topics Utilisation efficace des informations géométriques pour le clustering et les sujets connexes

Tetsuo ASANO

  • Vues en texte intégral

    0

  • Citer

Résumé:

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 3 jusqu'à k est une constante fixe. Pour le cas k=2, l'utilisation efficace des propriétés géométriques d'une solution optimale conduit à une amélioration considérable de la complexité de calcul. D'autres sujets connexes sont également abordés.

Publication
IEICE TRANSACTIONS on Information Vol.E83-D No.3 pp.418-427
Date de publication
2000/03/25
Publicisé
ISSN en ligne
DOI
Type de manuscrit
INVITED SURVEY PAPER
Catégories
Algorithmes pour les problèmes géométriques

Auteurs

Mots-clés

Table des matières