A linear-time algorithm for finding an ambitus (Q1186786)

The paper presents a linear algorithm for finding an ambitus in a 2- connected graph \(G\). Let \(s\), \(t\) be two distinct vertices of \(G\) and \(P\), \(Q\) two internally disjoint \(s-t\) paths in \(G\). These two paths form an ambitus in \(G\) if components of \(G-(P\cup Q)\) called bridges and divided into groups \(B^ P\), \(B^ Q\), \(B^{PQ}\) satisfy the property that a bridge in one group does not interlace with any bridge in the other group. That means an ambitus is a cycle cutting the graph into disjoint pieces which can be investigated separately. Fast finding an ambitus makes it possible to employ the divide-and-conquer paradigm in designing some graph algorithms.