Skip to content

Constraint Programming and Google Scholar

I am in Cork, Ireland for this year’s CP/AI-OR conference. This is a conference series that revolves around issues that constraint programming and operations research have in common: integration of techniques, applications, software systems and so on. I really like this conference series (disclosure: I am on the steering committee for the conference, so I would like it to be successful!). Like many computer science conferences, and unlike most OR conferences, this is a competitive conference with a rejection rate close to 80%. So the quality is high, but the number of participants is somewhat low: nothing like rejecting a submission to discourage participation! But the small size (about 60) means an opportunity to talk to lots of people.

Being in Ireland, we naturally ended the evening with a pint of beer (Murphy’s or Guinness for the cool people, lagers for the others), and we started discussing the most referenced papers in constraint programming or satisfiability (according to Google Scholar: see my OR version of this). Checking a few possibilities, here are some data, though I think this can be improved:

“A Computing Procedure for Quantification Theory” by Davis and Putnam, 1002 references (the fundamental algorithm for SAT solvers)
“Chaff: Engineering an Efficient SAT Solver” by Moskewicz, Madigan, Zhao, Zhang, and Malik: 880 references

“Partial Constraint Satisfaction” by Freuder and Wallace, 447 references

“Generalized Arc Consistency for Global Cardinality Constraint” by Regin (my favorite!), 128 references

Constraint Programming in Logic Programming, van Hentenryck 731 (book)

“Temporal Constraint Networks” by Dechter, Meiri, and Pearl, 710 references

Again, you are welcome to post other high ranking papers and books!

Update June 6, 2006

Both Pascal van Hentenryck and Diego Olivier Fernandez Pons point out that Régin’s most cited paper requires the “é” to find. I wondered where the alldiff paper went!

A filtering algorithm for constraints of difference in CSPs
JC Régin – Proceedings of the twelfth national conference on Artificial Intelligence has 285 cites in Google scholar.

It is interesting that Google Scholar seems smart enough to combine papers with slightly different spellings: there are no cites without the “é” of the above, and no cites with an “é” in the gcc paper cited earlier.