| Téléchargement | - Voir le manuscrit accepté : Linear-space algorithms for distance preserving embedding (PDF, 287 Kio)
|
|---|
| Auteur | Rechercher : Asano, T.; Rechercher : Bose, P.; Rechercher : Carmi, P.; Rechercher : Maheshwari, A.; Rechercher : Shu, Chang; Rechercher : Smid, M.; Rechercher : Wuhrer, Stefanie |
|---|
| Format | Texte, Article |
|---|
| Conférence | Canadian Conference on Computational Geometry, August 20-22, 2007, Ottawa, Ontario, Canada |
|---|
| Résumé | Le problème de l'intégration de graphes préservant la distance consiste à intégrer les sommets d'un graphe pondéré donné dans des points d'un espace euclidien bidimensionnel de sorte que, pour chaque arête, la distance entre les points terminaux correspondants soit la proche possible du poids de l'arête. Si le graphe donné est complet, c'est-à-dire si les contraintes de distance sont fournies en tant que matrice complète, alors l'analyse des coordonnées principales peut le résoudre dans un temps polynomial. Un grave inconvénient est son exigence d'espace quadratique. Dans cet article, nous développons des algorithmes en espace linéaire pour résoudre ce problème. Une idée clé consiste à partitionner un ensemble de n objets en sous-ensembles disjoints (grappes) de taille O(pn), de sorte que la distance minimum entre les grappes soit maximisée parmi toutes les partitions possibles. |
|---|
| Date de publication | 2007 |
|---|
| Dans | |
|---|
| Langue | anglais |
|---|
| Numéro du CNRC | NRCC 49830 |
|---|
| Numéro NPARC | 8914111 |
|---|
| Exporter la notice | Exporter en format RIS |
|---|
| Signaler une correction | Signaler une correction (s'ouvre dans un nouvel onglet) |
|---|
| Identificateur de l’enregistrement | 3bc87f0b-6635-4d88-a0f8-ae2e34ec8886 |
|---|
| Enregistrement créé | 2009-04-22 |
|---|
| Enregistrement modifié | 2020-08-12 |
|---|
