This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or E-far from k-edge-connectivity. This is the first testing algorithm for k-edge- connectivity of digraphs whose ...This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or E-far from k-edge-connectivity. This is the first testing algorithm for k-edge- connectivity of digraphs whose running time is independent of the number of vertices and edges. A digraph of n vertices with degree bound d is ε-far from k-edge-connectivity if at least εdn edges have to be added or deleted to make the digraph k-edge-connected, preserving the degree bound. Given a constant error parameter ε and a degree bound d, our algorithm always accepts all k-edge-connected digraphs and reiects all digraphs that is ε-far from k-edge-connectivity with orobabilitv at least 2/3.It runs in O（d（εd^-c）^k logεd^-1O）（c〉1 is a constant）time when input digraphs are restricted to be （k-1）-edge connected and runs in O（d（εd^-ck）^klogεd^-kO）（c〉1 is a constant）time for general digraphs.展开更多
文摘This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or E-far from k-edge-connectivity. This is the first testing algorithm for k-edge- connectivity of digraphs whose running time is independent of the number of vertices and edges. A digraph of n vertices with degree bound d is ε-far from k-edge-connectivity if at least εdn edges have to be added or deleted to make the digraph k-edge-connected, preserving the degree bound. Given a constant error parameter ε and a degree bound d, our algorithm always accepts all k-edge-connected digraphs and reiects all digraphs that is ε-far from k-edge-connectivity with orobabilitv at least 2/3.It runs in O（d（εd^-c）^k logεd^-1O）（c〉1 is a constant）time when input digraphs are restricted to be （k-1）-edge connected and runs in O（d（εd^-ck）^klogεd^-kO）（c〉1 is a constant）time for general digraphs.
