The impact of problem structure on search is a relevant issue in artificial intelligence and related areas. Among the possible approaches to analyze problem structure, the one referring to constraint graph enables to relate graph parameters and characteristics with search algorithm behavior. In this work, we investigate the behavior of local search applied to SAT instances associated to graphs with small-world topology. Small-world graphs, such as friendship networks, have low characteristic path length and high clustering. In this work, we first present a procedure to generate SAT instances characterized by a constraint graph with a small-world topology. Then we show experimental results concerning the behavior of local search algorithms applied to this benchmark.

On the impact of small-world constraint graphs on local search / A.Roli. - ELETTRONICO. - (2004), pp. 33-47. (Intervento presentato al convegno LSCS2004 - 1st International Workshop on Local Search Techniques in Constraint Satisfaction tenutosi a Toronto (Canada) nel 27 September 2004).

On the impact of small-world constraint graphs on local search

ROLI, ANDREA
2004

Abstract

The impact of problem structure on search is a relevant issue in artificial intelligence and related areas. Among the possible approaches to analyze problem structure, the one referring to constraint graph enables to relate graph parameters and characteristics with search algorithm behavior. In this work, we investigate the behavior of local search applied to SAT instances associated to graphs with small-world topology. Small-world graphs, such as friendship networks, have low characteristic path length and high clustering. In this work, we first present a procedure to generate SAT instances characterized by a constraint graph with a small-world topology. Then we show experimental results concerning the behavior of local search algorithms applied to this benchmark.
2004
Proceedings of LSCS2004 - 1st International Workshop on Local Search Techniques in Constraint Satisfaction
33
47
On the impact of small-world constraint graphs on local search / A.Roli. - ELETTRONICO. - (2004), pp. 33-47. (Intervento presentato al convegno LSCS2004 - 1st International Workshop on Local Search Techniques in Constraint Satisfaction tenutosi a Toronto (Canada) nel 27 September 2004).
A.Roli
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/37307
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact