Treffer: New algorithms to compute the strength of a graph
Title:
New algorithms to compute the strength of a graph
Authors:
Contributors:
Algorithms, simulation, combinatorics and optimization for telecommunications (MASCOTTE), Centre Inria d'Université Côte d'Azur, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-COMmunications, Réseaux, systèmes Embarqués et Distribués (Laboratoire I3S - COMRED), Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S), Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA)-Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA), Orange Labs Projet COST 293 (GRAAL) Projet AEOLUS, INRIA
Source:
[Research Report] RR-6592. :17-17
Publisher Information:
CCSD, 2008.
Publication Year:
2008
Collection:
collection:UNICE
collection:CNRS
collection:INRIA
collection:INRIA-SOPHIA
collection:INRIA-RRRT
collection:I3S
collection:INRIASO
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:TDS-MACS
collection:LARA
collection:UNIV-COTEDAZUR
collection:TEST-NICE
collection:CNRS
collection:INRIA
collection:INRIA-SOPHIA
collection:INRIA-RRRT
collection:I3S
collection:INRIASO
collection:INRIA_TEST
collection:TESTALAIN1
collection:INRIA2
collection:TDS-MACS
collection:LARA
collection:UNIV-COTEDAZUR
collection:TEST-NICE
Subject Terms:
strength of a graph, matroid, partition, connectivity, community detection, small-world, ACM: G.: Mathematics of Computing, G.2: DISCRETE MATHEMATICS, G.2.2: Graph Theory, G.2.2.0: Graph algorithms, G.2.1: Combinatorics, G.2.1.0: Combinatorial algorithms, G.2.3: Applications, ACM: F.: Theory of Computation, F.2: ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY, F.2.2: Nonnumerical Algorithms and Problems, F.2.2.6: Sorting and searching, [INFO.INFO-DS]Computer Science [cs], Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs], Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math], Combinatorics [math.CO], [INFO.INFO-NI]Computer Science [cs], Networking and Internet Architecture [cs.NI]
Original Identifier:
HAL:
Document Type:
Report
report<br />Reports
Language:
English
Access URL:
Rights:
info:eu-repo/semantics/OpenAccess
Accession Number:
edshal.inria.00305560v2
Database:
HAL
Weitere Informationen
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.