Based on detailed analysis of advantages and disadvantages of the existing connected-component labeling (CCL) algorithm,a new algorithm for binary connected components labeling based on run-length encoding (RLE) a...Based on detailed analysis of advantages and disadvantages of the existing connected-component labeling (CCL) algorithm,a new algorithm for binary connected components labeling based on run-length encoding (RLE) and union-find sets has been put forward.The new algorithm uses RLE as the basic processing unit,converts the label merging of connected RLE into sets grouping in accordance with equivalence relation,and uses the union-find sets which is the realization method of sets grouping to solve the label merging of connected RLE.And the label merging procedure has been optimized:the union operation has been modified by adding the "weighted rule" to avoid getting a degenerated-tree,and the "path compression" has been adopted when implementing the find operation,then the time complexity of label merging is O(nα(n)).The experiments show that the new algorithm can label the connected components of any shapes very quickly and exactly,save more memory,and facilitate the subsequent image analysis.展开更多
Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgra...Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.展开更多
1引言
F. F.Codd于七十年代提出了著名的关系数据库模型,经过几十年发展,以它为基础的关系数据库系统得到了广泛的流行和认可,它有着层次模型和网状模型无可比拟的优点,如灵活性、逻辑和物理独立性、数据完整性等.然而,它也有自身的不足...1引言
F. F.Codd于七十年代提出了著名的关系数据库模型,经过几十年发展,以它为基础的关系数据库系统得到了广泛的流行和认可,它有着层次模型和网状模型无可比拟的优点,如灵活性、逻辑和物理独立性、数据完整性等.然而,它也有自身的不足,就是对于不确定性的数据处理能力较差.展开更多
A new expression of vague sets is given. Based on the reference [3,4],we discuss the definition of intersec-tion and union and some properties of vague set again ,then similarity measure and examples are presented.
文摘Based on detailed analysis of advantages and disadvantages of the existing connected-component labeling (CCL) algorithm,a new algorithm for binary connected components labeling based on run-length encoding (RLE) and union-find sets has been put forward.The new algorithm uses RLE as the basic processing unit,converts the label merging of connected RLE into sets grouping in accordance with equivalence relation,and uses the union-find sets which is the realization method of sets grouping to solve the label merging of connected RLE.And the label merging procedure has been optimized:the union operation has been modified by adding the "weighted rule" to avoid getting a degenerated-tree,and the "path compression" has been adopted when implementing the find operation,then the time complexity of label merging is O(nα(n)).The experiments show that the new algorithm can label the connected components of any shapes very quickly and exactly,save more memory,and facilitate the subsequent image analysis.
文摘Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u.For any UV(G),let N(U)=∪_~u∈U N(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K_~1,3 .One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al.: Let G be a 2-connected claw-free graph of order n,and d(u)+d(v)+d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that,for any three positive integers s,t and w,such that if G is a (s+t+w-1)-connected claw-free graph of order n,and d(S)+d(T)+d(W)>n-(s+t+w) for every three disjoint independent vertex sets S,T,W with |S|=s,|T|=t,|W|=w,and S∪T∪W is also independent,then G is Hamiltonian.Other related results are obtained too.
文摘A new expression of vague sets is given. Based on the reference [3,4],we discuss the definition of intersec-tion and union and some properties of vague set again ,then similarity measure and examples are presented.