Geodesic
Expected number of locally maximal solutions for random Boolean CSPs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007).

Voir la notice de l'article provenant de la source Episciences

For a large number of random Boolean constraint satisfaction problems, such as random $k$-SAT, we study how the number of locally maximal solutions evolves when constraints are added. We give the exponential order of the expected number of these distinguished solutions and prove it depends on the sensitivity of the allowed constraint functions only. As a by-product we provide a general tool for computing an upper bound of the satisfiability threshold for any problem of a large class of random Boolean CSPs. 
@article{DMTCS_2007_special_253_a21,
     author = {Creignou, Nadia and Daud\'e, Herv\'e and Dubois, Olivier},
     title = {Expected number of locally maximal solutions for random {Boolean} {CSPs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)},
     year = {2007},
     doi = {10.46298/dmtcs.3539},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3539/}
}
TY  - JOUR
AU  - Creignou, Nadia
AU  - Daudé, Hervé
AU  - Dubois, Olivier
TI  - Expected number of locally maximal solutions for random Boolean CSPs
JO  - Discrete mathematics & theoretical computer science
PY  - 2007
VL  - DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3539/
DO  - 10.46298/dmtcs.3539
LA  - en
ID  - DMTCS_2007_special_253_a21
ER  - 
%0 Journal Article
%A Creignou, Nadia
%A Daudé, Hervé
%A Dubois, Olivier
%T Expected number of locally maximal solutions for random Boolean CSPs
%J Discrete mathematics & theoretical computer science
%D 2007
%V DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3539/
%R 10.46298/dmtcs.3539
%G en
%F DMTCS_2007_special_253_a21
Creignou, Nadia; Daudé, Hervé; Dubois, Olivier. Expected number of locally maximal solutions for random Boolean CSPs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS Proceedings vol. AH, 2007 Conference on Analysis of Algorithms (AofA 07) (2007). doi : 10.46298/dmtcs.3539. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3539/

Cité par Sources :