Algorithms for finding a rooted (k,1)-edge-connected orientation

A digraph is called rooted (k,1)-edge-connected if it has a root node r0 such that there exist k arc-disjoint paths from r0 to every other node and there is a path from every node to r0. Here we give a simple algorithm for finding a (k,1)-edge-connected orientation of a graph. A slightly more complicated variation of this algorithm has running time O(n4+n2m) that is better than the time bound of the previously known algorithms. With the help of this algorithm one can check whether an undirected graph is highly k-tree-connected, that is, for each edge e of the graph G, there are k edge-disjoint spanning trees of G not containing e. High tree-connectivity plays an important role in the investigation of redundantly rigid body-bar graphs.