TY - GEN
T1 - A note on treewidth in random graphs
AU - Wang, Chaoyi
AU - Liu, Tian
AU - Cui, Peng
AU - Xu, Ke
PY - 2011
Y1 - 2011
N2 - We show that in Erdocombining double acute accents-Rényi random graph G(n,p) with high probability, when p = c/n and c is a constant, the treewidth is upper bounded by tn for some constant t < 1 which may depend on c, but when p ≫ 1/n, the treewidth is lower bounded by n - o(n). The upper bound refutes a conjecture that treewidth in G(n,p = c/n) is as large as n - o(n), and the lower bound provides further theoretical evidence on hardness of some random constraint satisfaction problems called Model RB and Model RD.
AB - We show that in Erdocombining double acute accents-Rényi random graph G(n,p) with high probability, when p = c/n and c is a constant, the treewidth is upper bounded by tn for some constant t < 1 which may depend on c, but when p ≫ 1/n, the treewidth is lower bounded by n - o(n). The upper bound refutes a conjecture that treewidth in G(n,p = c/n) is as large as n - o(n), and the lower bound provides further theoretical evidence on hardness of some random constraint satisfaction problems called Model RB and Model RD.
UR - https://www.scopus.com/pages/publications/80051988915
U2 - 10.1007/978-3-642-22616-8_38
DO - 10.1007/978-3-642-22616-8_38
M3 - 会议稿件
AN - SCOPUS:80051988915
SN - 9783642226151
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 491
EP - 499
BT - Combinatorial Optimization and Applications - 5th International Conference, COCOA 2011, Proceedings
T2 - 5th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2011
Y2 - 4 August 2011 through 6 August 2011
ER -