Testing k-Edge-Connectivity of Digraphs

Yuichi Yoshida, Hiro ItoIEICE 2007

Abstract

This paper presents an algorithm that tests whether a given degree-bounded digraph is k-edge-connected or ɛ-far from k-edge-connectivity. This is the first testing algorithm for k-edgeconnectivity 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 rejects all digraphs that is ɛ-far from k-edge-connectivity with probability at least 2/3. It runs in $$ O\left( {d\left( {\frac{c} {{\varepsilon d}}} \right)^k log\frac{1} {{\varepsilon d}}O} \right) $$ (c > 1 is a constant) time when input digraphs are restricted to be (k-1)-edge connected and runs in $$ O\left( {d\left( {\frac{{ck}} {{\varepsilon d}}} \right)^k log\frac{k} {{\varepsilon d}}O} \right) $$ (c > 1 is a constant) time for general digraphs.
BibTeX
@inproceedings{yoshida2007testing,
  author = {Yuichi Yoshida and Hiro Ito},
  title = {{Testing k-Edge-Connectivity of Digraphs}},
  booktitle = {IEICE},
  year = {2007},
}

Loading related content...

Figure