Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditi...Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditions: (1) Every leaf of G-A has a connected cotree and (2) The set of bridges of G-B(G-A) is A, where B(G-A) is the set of bridges of G-A. An efficient algorithm on finding a smooth frame decompositi on of a graph is provided.展开更多
Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibilit...Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibility of solving some intractable problems. In the proposed procedure,vertex building blocks consisting of 3,4-armed branched junction molecules are selectively used to form different graph structures. After separating these graph structures by gel electrophoresis,the connec-tivity of this graph can be determined. Furthermore,the amount of potential solutions can be reduced by a theorem of graph theory.展开更多
为了解决在大规模组播网络上进行有效的故障定位中手工故障定位效率低的问题,根据组播网络拓扑特点提出了基于图论的网络可达性故障定位问题的数学模型。在此基础上,提出两种故障定位算法,即基于经验的路径加权法和基于图论的连通图算...为了解决在大规模组播网络上进行有效的故障定位中手工故障定位效率低的问题,根据组播网络拓扑特点提出了基于图论的网络可达性故障定位问题的数学模型。在此基础上,提出两种故障定位算法,即基于经验的路径加权法和基于图论的连通图算法。算法可以有效地在大规模组播网络上进行自动故障定位,提高了故障定位的效率。基于中国教育和科研计算机网(Ch ina education and researchnetw ork,CERNET)组播网络拓扑结构的数据模拟验证了算法的有效性。展开更多
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.展开更多
文摘Let G be a graph and A be a subset of the edges of G. A frame decomposition of G is a pair (G-A,A) such t ha t G-A is connected. A smooth frame decomposition of G is a frame decompo sition satisfying the two conditions: (1) Every leaf of G-A has a connected cotree and (2) The set of bridges of G-B(G-A) is A, where B(G-A) is the set of bridges of G-A. An efficient algorithm on finding a smooth frame decompositi on of a graph is provided.
基金Supported by the National Natural Science Foundation of China (No.30370356 and No.60574041).
文摘Inspired by the potential computational capability of 3-Dimensional (3D) DNA structure,this paper presents a graph structure constructed by k-armed (k = 3or 4) branched junction DNA molecules to explore the possibility of solving some intractable problems. In the proposed procedure,vertex building blocks consisting of 3,4-armed branched junction molecules are selectively used to form different graph structures. After separating these graph structures by gel electrophoresis,the connec-tivity of this graph can be determined. Furthermore,the amount of potential solutions can be reduced by a theorem of graph theory.
文摘为了解决在大规模组播网络上进行有效的故障定位中手工故障定位效率低的问题,根据组播网络拓扑特点提出了基于图论的网络可达性故障定位问题的数学模型。在此基础上,提出两种故障定位算法,即基于经验的路径加权法和基于图论的连通图算法。算法可以有效地在大规模组播网络上进行自动故障定位,提高了故障定位的效率。基于中国教育和科研计算机网(Ch ina education and researchnetw ork,CERNET)组播网络拓扑结构的数据模拟验证了算法的有效性。
文摘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.
