An Investigation of Variable Relationships in 3-SAT Problems

Kravchuk, Olena, Pullan, Wayne, Thornton, John and Sattar, Abdul (2002). An Investigation of Variable Relationships in 3-SAT Problems. In: Bob McKay and John Slaney, Lecture Notes in Computer Science: AI 2002 - Advances in Artificial Intelligence. 15th Australian Joint Conference on Artificial Intelligence, Canberra, Australia, (579-590). 2–6 December 2002.


Author Kravchuk, Olena
Pullan, Wayne
Thornton, John
Sattar, Abdul
Title of paper An Investigation of Variable Relationships in 3-SAT Problems
Conference Paper Type Fully Published Paper
Conference name 15th Australian Joint Conference on Artificial Intelligence
DOI 10.1007/3-540-36187-1_51
Conference location Canberra, Australia
Conference dates 2–6 December 2002
Proceedings title Lecture Notes in Computer Science: AI 2002 - Advances in Artificial Intelligence   Check publisher's open access policy
Journal name Al 2002: Advances in Artificial Intelligence   Check publisher's open access policy
Editor Bob McKay
John Slaney
Place published Berlin, Germany
Publisher Springer Berlin
Publication date 2002
Volume number 2557
ISBN 3-540-00197-2; 978-3-540-00197-3
ISSN 0302-9743
Start page 579
End page 590
Total pages 12
Language eng
Abstract/Summary To date, several types of structure for finite Constraint Satisfaction Problems have been investigated with the goal of either improving the performance of problem solvers or allowing efficient problem solvers to be identified. Our aim is to extend the work in this area by performing a structural analysis in terms of variable connectivity for 3-SAT problems. Initially structure is defined in terms of the compactness of variable connectivity for a problem. Using an easily calculable statistic developed to measure this compactness, a test was then created for identifying 3-SAT problems as either compact, loose or unstructured (or uniform). A problem generator was constructed for generating 3-SAT problems with varying degrees of structure. Using problems from this problem generator and existing problems from SATLIB, we investigated the effects of this type of structure on satisfiability and solvability of 3-SAT problems. For the same problem length, it is demonstrated that satisfiability and solvability are different for structured and uniform problems generated by the problem generator.
Subjects 0801 Artificial Intelligence and Image Processing
E1
Keyword Computer Science, Artificial Intelligence
constraints
search
Q-Index Code E1
Additional Notes From t.p.: "AI 2002: Advances in Artificial Intelligence: 15th Australian Joint Conference on Artificial Intelligence Canberra, Australia, December 2-6, 2002, Proceedings"

Document type: Conference Paper
Sub-type: Fully Published Paper
Collections: Excellence in Research Australia (ERA) - Collection
School of Agriculture and Food Sciences
 
Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 1 times in Thomson Reuters Web of Science Article | Citations
Google Scholar Search Google Scholar
Access Statistics: 65 Abstract Views  -  Detailed Statistics
Created: Wed, 17 Oct 2007, 11:53:06 EST