New algorithms to compute the strength of a graph

Jérôme Galtier (1)

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications

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.

Mots clés: strength of a graph; matroid; partition; connectivity; community detection; small-world

Domaines: Algorithme et structure de données [cs.DS]; Mathématique discrète [cs.DM]; Combinatoire [math.CO]; Réseaux et télécommunications [cs.NI]

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