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 ...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.展开更多
An approximation algorithm is presented for augmenting an undirected weightedgraph to a K-edge-connected graph.The algorithm is useful for designing a reliable network.
The generalized kt-connectivity K(k)(G)and k-edge-connectivityλ_(k)(G)of a graph G are a natural generalization of traditional connectivity K(G)and edge connectivityλ(G),respectively,which for K(G)=K_(2)(G)andλ(G)=...The generalized kt-connectivity K(k)(G)and k-edge-connectivityλ_(k)(G)of a graph G are a natural generalization of traditional connectivity K(G)and edge connectivityλ(G),respectively,which for K(G)=K_(2)(G)andλ(G)=λ_(2)(G).They are important parameters which can often be used to measure the reliability and fault tolerance of interconnection networks.CRNs is a new family of composite networks based on the complete graph,which contain common networks and have the same structural properties as alter-nating group network,and may also include some unknown networks.In this paper,we investigate the generalized 3-connectivity and 3-edge-connectivity of CRNs,and show that K_(3)(G_(l),m)=λ_(3)(G_(l)m)=m-2.展开更多
A graphic sequence π =(d1, d2,..., dn) is said to be forcibly k-edge-connected if every realization of π is k-edge-connected. In this paper, we obtain a new sufficient degree condition for π to be forcibly k-edgeco...A graphic sequence π =(d1, d2,..., dn) is said to be forcibly k-edge-connected if every realization of π is k-edge-connected. In this paper, we obtain a new sufficient degree condition for π to be forcibly k-edgeconnected. We also show that this new sufficient degree condition implies a strongest monotone degree condition for π to be forcibly 2-edge-connected and a conjecture about a strongest monotone degree condition for π to be forcibly 3-edge-connected due to Bauer et al.(Networks, 54(2)(2009) 95-98), and also implies a strongest monotone degree condition for π to be forcibly 4-edge-connected.展开更多
文摘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.
文摘An approximation algorithm is presented for augmenting an undirected weightedgraph to a K-edge-connected graph.The algorithm is useful for designing a reliable network.
基金supported by the Innovation Projects of Qinghai Minzu University(No.07M2024008)AFSFQH(No.2022-ZJ-753).
文摘The generalized kt-connectivity K(k)(G)and k-edge-connectivityλ_(k)(G)of a graph G are a natural generalization of traditional connectivity K(G)and edge connectivityλ(G),respectively,which for K(G)=K_(2)(G)andλ(G)=λ_(2)(G).They are important parameters which can often be used to measure the reliability and fault tolerance of interconnection networks.CRNs is a new family of composite networks based on the complete graph,which contain common networks and have the same structural properties as alter-nating group network,and may also include some unknown networks.In this paper,we investigate the generalized 3-connectivity and 3-edge-connectivity of CRNs,and show that K_(3)(G_(l),m)=λ_(3)(G_(l)m)=m-2.
基金supported by the Hainan Provincial Natural Science Foundation of China(No.2019RC085)the National Natural Science Foundation of China(No.11961019)。
文摘A graphic sequence π =(d1, d2,..., dn) is said to be forcibly k-edge-connected if every realization of π is k-edge-connected. In this paper, we obtain a new sufficient degree condition for π to be forcibly k-edgeconnected. We also show that this new sufficient degree condition implies a strongest monotone degree condition for π to be forcibly 2-edge-connected and a conjecture about a strongest monotone degree condition for π to be forcibly 3-edge-connected due to Bauer et al.(Networks, 54(2)(2009) 95-98), and also implies a strongest monotone degree condition for π to be forcibly 4-edge-connected.
