umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Locality and hard SAT-instances
Umeå University, Faculty of Science and Technology, Mathematics and Mathematical Statistics.
2006 (English)In: Journal on Satisfiability, Boolean Modeling and Computation, Vol. 2Article in journal (Refereed) Published
Abstract [en]

In this note we construct a family of SAT-instance based on Eulerian graphs which are aimed at being hard for resolution based SAT-solvers. We discuss some experiments made with instances of this type and how a solver can try to avoid at least some of the pitfalls presented by these instances. Finally we look at how the density of subformulae can influence the hardness of SAT instances.

Place, publisher, year, edition, pages
2006. Vol. 2
Identifiers
URN: urn:nbn:se:umu:diva-7601OAI: oai:DiVA.org:umu-7601DiVA: diva2:147272
Available from: 2008-01-11 Created: 2008-01-11 Last updated: 2011-01-11Bibliographically approved

Open Access in DiVA

No full text

Search in DiVA

By author/editor
Markström, Klas
By organisation
Mathematics and Mathematical Statistics

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 59 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf