In graph theory, the strength of an undirected graph corresponds to the minimum ratio of edges removed/components created in a decomposition of the graph in question. It is a method to compute partitions of the set of vertices and detect zones of high concentration of edges, and is analogous to graph toughness which is defined similarly for vertex removal.
Definitions The strength σ ( G ) {\displaystyle \sigma (G)} of an undirected simple graph G = (V, E) admits the three following definitions:
Let Π {\displaystyle \Pi } be the set of all partitions of V {\displaystyle V} , and ∂ π {\displaystyle \partial \pi } be the set of edges crossing over the sets of the partition π ∈ Π {\displaystyle \pi \in \Pi } , then σ ( G ) = min π ∈ Π | ∂ π | | π | − 1 {\displaystyle \displaystyle \sigma (G)=\min _{\pi \in \Pi }{\frac {|\partial \pi |}{|\pi |-1}}} . Also if T {\displaystyle {\mathcal {T}}} is the set of all spanning trees of G, then
σ ( G ) = max { ∑ T ∈ T λ T : ∀ T ∈ T λ T ≥ 0 and ∀ e ∈ E ∑ T ∋ e λ T ≤ 1 } . {\displaystyle \sigma (G)=\max \left\{\sum _{T\in {\mathcal {T}}}\lambda _{T}\ :\ \forall T\in {\mathcal {T}}\ \lambda _{T}\geq 0{\mbox{ and }}\forall e\in E\ \sum _{T\ni e}\lambda _{T}\leq 1\right\}.}
And by linear programming duality,
σ ( G ) = min { ∑ e ∈ E y e : ∀ e ∈ E y e ≥ 0 and ∀ T ∈ T ∑ e ∈ E y e ≥ 1 } . {\displaystyle \sigma (G)=\min \left\{\sum _{e\in E}y_{e}\ :\ \forall e\in E\ y_{e}\geq 0{\mbox{ and }}\forall T\in {\mathcal {T}}\ \sum _{e\in E}y_{e}\geq 1\right\}.}
Complexity Computing the strength of a graph can be done in polynomial time, and the first such algorithm was discovered by Cunningham (1985). The algorithm with best complexity for computing exactly the strength is due to Trubin (1993), uses the flow decomposition of Goldberg and Rao (1998), in time O ( min ( m , n 2 / 3 ) m n log ( n 2 / m + 2 ) ) {\displaystyle O(\min({\sqrt {m}},n^{2/3})mn\log(n^{2}/m+2))} .
… excerpt ends here. Continue reading the full article.
