论文部分内容阅读
This paper presents an algorithm that tests whether a given degree-bounded digraph is κ-edge-connected or ε-far from κ-edge-connectivity. This is the first testing algorithm for κ-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 κ-edge-connectivity if at least εdn edges have to be added or deleted to make the digraph κ-edge-connected, preserving the degree bound. Given a constant error parameter ε and a degree bound d, our algorithm always accepts all κ-edge-connected digraphs and rejects all digraphs that is ε-far from κ-edge-connectivity with probability at least 2/3. It runs in O(d (c/εd)~κlog 1/εd O)(c > 1 is a constant) time when input digraphs are restricted to be (κ- 1)-edge connected and runs in O(d (cκ/εd)~κ log κ/εdO)(c > 1 is a constant) time for general digraphs.