Average-case complexity of backtrack search for coloring sparse random graphs

作者：

Highlights：

• We estimate the asymptotic complexity of coloring sparse random graphs.

• For graphs Gn,p(n), where p(n)→0, the complexity tends to infinity.

• For p(n)=d/n, where d is constant, the expected complexity is exponential in n.

• If p(n)→0 sufficiently slowly, the expected number of steps is polynomial in n.

摘要

•We estimate the asymptotic complexity of coloring sparse random graphs.•For graphs Gn,p(n), where p(n)→0, the complexity tends to infinity.•For p(n)=d/n, where d is constant, the expected complexity is exponential in n.•If p(n)→0 sufficiently slowly, the expected number of steps is polynomial in n.

论文关键词：Graph coloring,Average-case complexity,Search tree,Random graphs,Backtrack

论文评审过程：Received 21 August 2011, Revised 4 May 2013, Accepted 17 June 2013, Available online 20 June 2013.

论文官网地址：https://doi.org/10.1016/j.jcss.2013.06.003