TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS  被引量:1

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[理学—数学]

 

参考文献:

正在载入数据...

 

二级参考文献:

正在载入数据...

 

耦合文献:

正在载入数据...

 

引证文献:

正在载入数据...

 

二级引证文献:

正在载入数据...

 

同被引文献:

正在载入数据...

 

相关期刊文献:

正在载入数据...

相关的主题
相关的作者对象
相关的机构对象