Kombinatorik und (parallele) Algorithmik/Komplexitätstheorie von SAT auf KNF-Teilklassen, insbesondere gemischte Hornformeln

• Applicant: Professor Dr. Ewald Speckenmeyer
• Subject Area: Theoretical Computer Science
• Term: from 2009 to 2014
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 110980500

• Final Report Year: 2015

Final Report Abstract

No abstract available

Publications

• Complexity Results for Linear XSAT-Problems, Proc. SAT 2010, Lecture Notes in Computer Science, Vol. 6175, 251-263 (2010)
  Porschen, S., Schmidt, T., Speckenmeyer, E.
  
• PARTIAL MAX-SAT of level graph (mixed-Horn)formulas, Studies in Logic, Vol. 3, Num. 3, 24-43 (2010)
  Speckenmeyer, E., Porschen, S.
  
• A Satisfiability-Based Approach for Embedding Generalized Tanglegrams on Level Graphs, Proc. SAT 2011, Lecture Notes in Computer Science, Vol. 6695, 134-144 (2011)
  Speckenmeyer, E., Wotzlaw, A., Porschen, S.
  
• Generalized k-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation. Discrete Applied Mathematics, Volume 160, Issues 16–17, November 2012, Pages 2349-2363
  Wotzlaw, A., Speckenmeyer, E., Porschen, S.
  (See online at https://doi.org/10.1016/j.dam.2012.05.028)
• pfolioUZK: Solver Description, Proc. of SAT Challenge 2012; Solver and Benchmark Descriptions, Department of Computer Science Series of Publications B, Vol. B-2012-2, University of Helsinki, 45 (2012)
  Wotzlaw, A., van der Grinten, A., Speckenmeyer, E., Porschen, S.
  
• Probabilistic Analysis of Random Mixed Horn Formulas, Forschungsbericht Univ. Köln (zaik2012-678) 2012
  Wotzlaw, A., Speckenmeyer, E., Porschen, S.
  
• satUZK: Solver Description, Proc. of SAT Challenge 2012; Solver and Benchmark Descriptions, Department of Computer Science Series of Publications B, Vol. B-2012-2, University of Helsinki, 54-55 (2012)
  van der Grinten, A., Wotzlaw, A., Speckenmeyer, E., Porschen, S.
  
• XSAT and NAE-SAT of linear CNF classes. Discrete Applied Mathematics, Volume 167, 20 April 2014, Pages 1-14
  Porschen, S., Schmidt, T., Speckenmeyer, E., Wotzlaw, A.
  (See online at https://doi.org/10.1016/j.dam.2013.10.030)