HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 Connect in order to contact the contributor
Submitted on : Tuesday, July 29, 2008 - 4:09:56 PM
Last modification on : Friday, February 4, 2022 - 3:19:13 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