Journal Title
Title of Journal: J Syst Sci Complex
|
Abbravation: Journal of Systems Science and Complexity
|
Publisher
Springer-Verlag
|
|
|
|
|
|
Authors: Yuichi Yoshida Hiro Ito
Publish Date: 2010/02/25
Volume: 23, Issue: 1, Pages: 91-101
Abstract
This paper presents an algorithm that tests whether a given degreebounded digraph is kedgeconnected or ɛfar from kedgeconnectivity This is the first testing algorithm for kedgeconnectivity 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 kedgeconnectivity if at least ɛdn edges have to be added or deleted to make the digraph kedgeconnected preserving the degree bound Given a constant error parameter ɛ and a degree bound d our algorithm always accepts all kedgeconnected digraphs and rejects all digraphs that is ɛfar from kedgeconnectivity with probability at least 2/3 It runs in Oleft dleft fracc varepsilon d rightk logfrac1 varepsilon dO right c 1 is a constant time when input digraphs are restricted to be k1edge connected and runs in Oleft dleft fracck varepsilon d rightk logfrack varepsilon dO right c 1 is a constant time for general digraphs
Keywords:
.
|
Other Papers In This Journal:
|