Random Hypergraphs and Subset SystemsOA
Random Hypergraphs and Subset Systems
Suppose to toss an independent coin with equal probability of success and failure for each subset of [n]={l,2,…,n},and form the random hypergraph H(n) by taking as hyperedges the subsets with successful cointosses.It is prove…查看全部>>
Suppose to toss an independent coin with equal probability of success and failure for each subset of [n]={l,2,…,n},and form the random hypergraph H(n) by taking as hyperedges the subsets with successful cointosses.It is proved that H(n) is almost surely connected.By defining a graph G(S) according toa subset system S,it is shown that the intersecting problem is NP-complete.
CHEN De-qiang;ZHENG Jie;WU Xiao-qian
College of Information Technology and Science,Nankai University,Tianjin 300071,ChinaDepartment of Applied Mathematics,Doughua University,Shanghai 201620,ChinaDepartment of Applied Mathematics,Doughua University,Shanghai 201620,China
数理科学
hypergraphsubset systemintersecting
hypergraphsubset systemintersecting
《东华大学学报（英文版）》 2008 (2)
222-224,3
评论