کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430054 | 687788 | 2013 | 15 صفحه PDF | دانلود رایگان |
• We estimate the asymptotic complexity of coloring sparse random graphs.
• For graphs Gn,p(n)Gn,p(n), where p(n)→0p(n)→0, the complexity tends to infinity.
• For p(n)=d/np(n)=d/n, where d is constant, the expected complexity is exponential in n.
• If p(n)→0p(n)→0 sufficiently slowly, the expected number of steps is polynomial in n.
We investigate asymptotically the expected number of steps taken by backtrack search for k -coloring random graphs Gn,p(n)Gn,p(n) or proving non-k -colorability, where p(n)p(n) is an arbitrary sequence tending to 0, and k is constant. Contrary to the case of constant p , where the expected runtime is known to be O(1)O(1), we prove that here the expected runtime tends to infinity. We establish how the asymptotic behavior of the expected number of steps depends on the sequence p(n)p(n). In particular, for p(n)=d/np(n)=d/n, where d is a constant, the runtime is always exponential, but it can be also polynomial if p(n)p(n) decreases sufficiently slowly, e.g. for p(n)=1/lnn.
Journal: Journal of Computer and System Sciences - Volume 79, Issue 8, December 2013, Pages 1287–1301