Exact phase transition of backtrack-free search with implications on the power of greedy algorithms

Simple item page
dc.creatorLi, Liang
dc.creatorLiu, Tian
dc.creatorXu, Ke
dc.date2008-11-19
dc.date.accessioned2026-07-07T10:19:27Z
dc.date.available2026-07-07T10:19:27Z
dc.descriptionBacktracking is a basic strategy to solve constraint satisfaction problems (CSPs). A satisfiable CSP instance is backtrack-free if a solution can be found without encountering any dead-end during a backtracking search, implying that the instance is easy to solve. We prove an exact phase transition of backtrack-free search in some random CSPs, namely in Model RB and in Model RD. This is the first time an exact phase transition of backtrack-free search can be identified on some random CSPs. Our technical results also have interesting implications on the power of greedy algorithms, on the width of random hypergraphs and on the exact satisfiability threshold of random CSPs.
dc.identifierhttps://arxiv.org/abs/0811.3055
dc.identifierhttp://arxiv.org/abs/0811.3055
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/174514
dc.subjectArtificial Intelligence
dc.subjectDiscrete Mathematics
dc.subjectData Structures and Algorithms
dc.titleExact phase transition of backtrack-free search with implications on the power of greedy algorithms
dc.typetext

Files

Collections

arXiv