2-edge-twinless blocks

12/31/2019

∙

by   Raed Jaberi, et al.

∙

0

∙

share

Let G=(V,E)) be a directed graph. A 2-edge-twinless block in G is a maximal vertex set C^t⊆ V of with |C^t|>1 such that for any distinct vertices v,w ∈ C^t, and for every edge e∈ E, the vertices v,w are in the same twinless strongly connected component of G∖ e. An edge e in a twinless strongly connected graph is a twinless bridge if the subgraph obtained from G by removing e is not twinless strongly connected. In this paper we show that the 2-edge-twinless blocks of G can be computed in O((b_tn+m)n) time, where b_t is the number of twinless bridges of G.