New algorithms to compute the strength of a graph

Jérôme Galtier 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We investigate the problem of computing the strength of a graph. We describe in this article the first polyhedral formulation for the weighted strength in polynomial size of the problem, that is O(mn), where n is the number of vertices and m the number of edges. Moreover, we describe a surprisingly simple FPTAS that gives the strength within 1+epsilon in time O(m log^2(n) log(m/n)/epsilon^2) and space O(m), outperforming by a factor of roughly min(n\sqrt{m},n^5/3) the best known exact algorithm of Trubin associated with the Goldberg and Rao maxflow algorithm for that problem, and of roughly sigma(G) the FPTAS of Plotkin, Shmoys, and Tardos.
Liste complète des métadonnées

Littérature citée [14 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00305560
Contributeur : Jerome Galtier <>
Soumis le : mardi 29 juillet 2008 - 16:09:56
Dernière modification le : mercredi 31 janvier 2018 - 10:24:04
Document(s) archivé(s) le : mercredi 29 mars 2017 - 15:09:17

Fichiers

RR-6592.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00305560, version 2

Citation

Jérôme Galtier. New algorithms to compute the strength of a graph. [Research Report] RR-6592, INRIA. 2008, pp.17. 〈inria-00305560v2〉

Partager

Métriques

Consultations de la notice

226

Téléchargements de fichiers

167