Afficher la notice abrégée

Constructing Incremental Sequences in Graphs

hal.structure.identifierLaboratoire Bordelais de Recherche en Informatique [LaBRI]
hal.structure.identifierAlgorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
dc.contributor.authorKLASING, Ralf
hal.structure.identifierInformatique, Biologie Intégrative et Systèmes Complexes [IBISC]
dc.contributor.authorLAFOREST, Christian
hal.structure.identifierSFU Discrete Mathematics Group [SFU-DMG]
dc.contributor.authorPETERS, Joseph G.
hal.structure.identifierInformatique, Biologie Intégrative et Systèmes Complexes [IBISC]
dc.contributor.authorTHIBAULT, Nicolas
dc.date.accessioned2024-04-15T09:53:47Z
dc.date.available2024-04-15T09:53:47Z
dc.date.issued2006
dc.identifier.issn1718-3235
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/198627
dc.description.abstractEnGiven a weighted graph G=(V,E,w), we investigate the problem of constructing a sequence of n=|V| subsets of vertices M_1,...,M_n (called groups) with small diameters, where the diameter of a group is calculated using distances in G. The constraint on these n groups is that they must be incremental: $M_1\subsetM_2 \subset...\subsetM_n=V$. The cost of a sequence is the maximum ratio between the diameter of each group $M_i$ and the diameter of a group $N_i^*$ with $i$ vertices and minimum diameter: $\max_2 \leqi \leqn \left \fracD(M_i)D(N_i^*) \right$. This quantity captures the impact of the incremental constraint on the diameters of the groups in a sequence. We give general bounds on the value of this ratio and we prove that the problem of constructing an optimal incremental sequence cannot be solved approximately in polynomial time with an approximation ratio less than 2 unless $P = NP$. Finally, we give a 4-approximation algorithm and we show that the analysis of our algorithm is tight.
dc.language.isoen
dc.publisherPreeminent Academic Facets
dc.title.enConstructing Incremental Sequences in Graphs
dc.typeArticle de revue
dc.subject.halSciences cognitives/Informatique
dc.subject.halInformatique [cs]/Recherche opérationnelle [cs.RO]
dc.subject.halInformatique [cs]/Algorithme et structure de données [cs.DS]
dc.subject.halInformatique [cs]/Mathématique discrète [cs.DM]
dc.subject.halInformatique [cs]/Informatique et théorie des jeux [cs.GT]
bordeaux.journalAlgorithmic Operations Research
bordeaux.page1--7
bordeaux.volume1
bordeaux.hal.laboratoriesLaboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800*
bordeaux.issue2
bordeaux.institutionUniversité de Bordeaux
bordeaux.institutionBordeaux INP
bordeaux.institutionCNRS
bordeaux.peerReviewedoui
hal.identifierhal-00341373
hal.version1
hal.popularnon
hal.audienceInternationale
hal.origin.linkhttps://hal.archives-ouvertes.fr//hal-00341373v1
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.jtitle=Algorithmic%20Operations%20Research&rft.date=2006&rft.volume=1&rft.issue=2&rft.spage=1--7&rft.epage=1--7&rft.eissn=1718-3235&rft.issn=1718-3235&rft.au=KLASING,%20Ralf&LAFOREST,%20Christian&PETERS,%20Joseph%20G.&THIBAULT,%20Nicolas&rft.genre=article


Fichier(s) constituant ce document

FichiersTailleFormatVue

Il n'y a pas de fichiers associés à ce document.

Ce document figure dans la(les) collection(s) suivante(s)

Afficher la notice abrégée