Skip to Main content Skip to Navigation

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 , Laboratoire I3S - 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Jerome Galtier <>
Submitted on : Tuesday, July 29, 2008 - 4:09:56 PM
Last modification on : Monday, October 12, 2020 - 10:30:12 AM
Long-term archiving on: : Wednesday, March 29, 2017 - 3:09:17 PM


Files produced by the author(s)


  • HAL Id : inria-00305560, version 2


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



Record views


Files downloads