0
$\begingroup$

I need an algorithm to calculate number of pair of vertices with at least 2 distinct paths between them in a undirected graph - the graph is connected - distinct paths = distinct edges ex: no. of vert = 3 and no. of edges = 3 and we have (1, 3) (1, 2) and (2, 3) valid paths from 1 to 2 are 1-3-2 and 1-2 - count only pairs (a,b) with a < b for example :

5(no. of vert) 6(no. of edges) : (1, 2) (2, 3) (3, 1) (3, 4) (4, 5) (5, 4).

Output is 4 :

(1, 2), (1, 3), (2, 3) and (4, 5).

$\endgroup$
  • 1
    $\begingroup$ I don't see any question here... $\endgroup$ – Yuval Filmus May 11 '18 at 16:30
  • $\begingroup$ Do you want distinct paths or disjoint paths? $\endgroup$ – Yuval Filmus May 11 '18 at 16:31
  • $\begingroup$ distinct paths, such in exemple $\endgroup$ – Karl May 11 '18 at 16:37
1
$\begingroup$

I'm assuming that you're looking for the number of pairs of vertices having two disjoint simple paths connected them. A pair of vertices has two disjoint simple paths connecting them if they are in the same biconnected component. You can partition the graph into biconnected components in linear time. If the biconnected components have sizes $N_i$, then the number of pairs is $\sum_i \binom{N_i}{2}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.