QQ客服 官方微博 反馈留言

	Large hinge width on sparse random hypergraphs
	Liu, Tian ; Lin, Xiaxiang ; Wang, Chaoyi ; Su, Kaile ; Xu, Ke
	2011
英文摘要	Consider random hypergraphs on n vertices, where each k-element subset of vertices is selected with probability p independently and randomly as a hyperedge. By sparse we mean that the total number of hyperedges is O(n) or O(n ln n). When k = 2, these are exactly the classical Erdos-Re??nyi random graphs G(n, p). We prove that with high probability, hinge width on these sparse random hypergraphs can grow linearly with the expected number of hyperedges. Some random constraint satisfaction problems such as Model RB and Model RD have satisfiability thresholds on these sparse constraint hypergraphs, thus the large hinge width results provide some theoretical evidence for random instances around satisfiability thresholds to be hard for a standard hinge-decomposition based algorithm. We also conduct experiments on these and other kinds of random graphs with several hundreds vertices, including regular random graphs and power law random graphs. The experimental results also show that hinge width can grow linearly with the number of edges on these different random graphs. These results may be of further interests.; EI; 0
语种	英语
DOI标识	10.5591/978-1-57735-516-8/IJCAI11-109
内容类型	其他
源URL	[http://ir.pku.edu.cn/handle/20.500.11897/295154]
专题	信息科学技术学院
推荐引用方式 GB/T 7714	Liu, Tian,Lin, Xiaxiang,Wang, Chaoyi,et al. Large hinge width on sparse random hypergraphs. 2011-01-01.

个性服务

查看访问统计

相关权益政策

暂无数据

收藏/分享

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。