TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS  

作　　者：Yuichi YOSHIDA.HiroI TO 

机构地区：[1]School of Informatics,Kyoto University

出　　处：《Journal of Systems Science & Complexity》2010年第1期91-101,共11页系统科学与复杂性学报（英文版）

摘　　要：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.

关 键 词：DIGRAPH GRAPH k-edge-connectivity property testing. 

分 类 号：O157.5[理学—数学]