Sur la difficulté de séparer un graphe par des plus courts chemins
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| dc.contributor.author | DIOT, Emilie | |
| hal.structure.identifier | Laboratoire Bordelais de Recherche en Informatique [LaBRI] | |
| hal.structure.identifier | Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE] | |
| hal.structure.identifier | Institut universitaire de France [IUF] | |
| dc.contributor.author | GAVOILLE, Cyril | |
| hal.structure.identifier | Laboratoire de Recherche en Informatique [LRI] | |
| dc.contributor.author | OCHEM, Pascal | |
| dc.contributor.editor | Ducourthial | |
| dc.contributor.editor | Bertrand et Felber | |
| dc.contributor.editor | Pascal | |
| dc.date.accessioned | 2024-04-15T09:47:33Z | |
| dc.date.available | 2024-04-15T09:47:33Z | |
| dc.date.issued | 2011 | |
| dc.date.conference | 2011 | |
| dc.identifier.uri | https://oskar-bordeaux.fr/handle/20.500.12278/198105 | |
| dc.description.abstract | Les schémas de routage et de calcul de distances les plus efficaces sont conçus à partir de décompositions hiérarchiques de la topologie en plus courts chemins. Ces constructions sont calculables efficacement pour de nombreuses topologies, comme les graphes planaires par exemple. Dans cet article nous montrons cependant que la décomposition d'une topologie arbitraire en $k$ plus courts chemins est NP-complet. | |
| dc.language.iso | fr | |
| dc.title | Sur la difficulté de séparer un graphe par des plus courts chemins | |
| dc.type | Communication dans un congrès | |
| dc.subject.hal | Informatique [cs]/Complexité [cs.CC] | |
| bordeaux.hal.laboratories | Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800 | * |
| bordeaux.institution | Université de Bordeaux | |
| bordeaux.institution | Bordeaux INP | |
| bordeaux.institution | CNRS | |
| bordeaux.conference.title | 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel) | |
| bordeaux.country | FR | |
| bordeaux.conference.city | Cap Estérel | |
| bordeaux.peerReviewed | oui | |
| hal.identifier | inria-00588312 | |
| hal.version | 1 | |
| hal.invited | non | |
| hal.proceedings | oui | |
| hal.popular | non | |
| hal.audience | Internationale | |
| hal.origin.link | https://hal.archives-ouvertes.fr//inria-00588312v1 | |
| bordeaux.COinS | ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Sur%20la%20difficult%C3%A9%20de%20s%C3%A9parer%20un%20graphe%20par%20des%20plus%20courts%20chemins&rft.atitle=Sur%20la%20difficult%C3%A9%20de%20s%C3%A9parer%20un%20graphe%20par%20des%20plus%20courts%20chemins&rft.date=2011&rft.au=DIOT,%20Emilie&GAVOILLE,%20Cyril&OCHEM,%20Pascal&rft.genre=unknown |
Fichier(s) constituant ce document
| Fichiers | Taille | Format | Vue |
|---|---|---|---|
|
Il n'y a pas de fichiers associés à ce document. |
|||