Journal articles

To appear.
  1. Peter Jonsson and Tomas Lööw: Computational Complexity of Linear Constraints over the Integers. Artificial Intelligence. To appear.

2012
  1. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen: Essential Convexity and Complexity of Semi-algebraic Constraints. Logical Methods in Computer Science. 8(4):article 5. link

  2. Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen: Horn versus Full First-order: Complexity Dichotomies in Algebraic Constraint Satisfaction. Journal of Logic and Computation 22:643-660, 2012. pdf

  3. Christer Bäckström and Peter Jonsson: Algorithms and Limits for Compact Plan Representation. Journal of Artificial Intelligence Research 44:141-177, 2012. link
2010
  1. Peter Jonsson and Johan Thapper: Approximability of Integer Programs with Positive Right-hand Sides. Information Processing Letters 110(10):351-355, 2010. pdf

  2. Tomás Feder, Pavol Hell, Peter Jonsson, Andrei Krokhin, and Gustav Nordh: Retractions to Pseudoforests. SIAM Journal on Discrete Mathematics 24(1):101-112, 2010. pdf

  3. Peter Jonsson and Gustav Nordh: Approximability of Clausal Constraints. Theory of Computing Systems 46(2):370-395, 2010. pdf

2009
  1. Robert Engström, Tommy Färnqvist, Peter Jonsson, and Johan Thapper: Properties of an Approximability-related Parameter on Circular Complete Graphs. Electronic Notes in Discrete Mathematics 35:115-120, 2009. pdf

  2. Peter Jonsson, Andrei Krokhin, and Fredrik Kuivinen: Hard Constraint Satisfaction Problems have Hard Gaps at Location 1. Theoretical Computer Science 410(38-40):3856-3874, 2009. pdf

2008
  1. Vladimir Deineko, Peter Jonsson, Mikael Klasson, and Andrei Krokhin: The Approximability of Max CSP with Fixed-value Constraints. Journal of the ACM 55:article 4, 2008. pdf

  2. Peter Jonsson and Andrei Krokhin: Computational Complexity of Auditing Finite Attributes in Statistical Databases. Journal of Computer and System Sciences 74:898-909, 2008. pdf

  3. Peter Jonsson, Fredrik Kuivinen, and Gustav Nordh: Max Ones Generalized to Larger Domains. SIAM Journal on Computing 38(1):329-365, 2008. pdf

2007
  1. Peter Jonsson and Andrei Krokhin: Maximum H-colourable Subdigraphs and Constraint Optimization with Arbitrary Weights. Journal of Computer and System Sciences 73(5):691-702, 2007. pdf

2006
  1. Peter Jonsson, Mikael Klasson, and Andrei Krokhin: The Approximability of Three-valued Max CSP. SIAM Journal on Computing 35(3):1329-1349, 2006. postscript

2005
  1. Peter Jonsson: Adding Clauses to Poor Man's Logic (without Increasing the Complexity). Journal of Applied Non-Classical Logics 15(3):341-357, 2005. postscript

  2. Vilhelm Dahllöf, Peter Jonsson, and Magnus Wahlström: Counting Models for 2SAT and 3SAT Formulae. Theoretical Computer Science 332(1-3):265-291, 2005. postscript / note

2004
  1. Peter Jonsson and Andrei Krokhin: Recognizing Frozen Variables in Constraint Satisfaction Problems. Theoretical Computer Science 329(1-3):93-113, 2004. postscript

  2. Víctor Dalmau and Peter Jonsson: The Complexity of Counting Homomorphisms Seen from the Other Side. Theoretical Computer Science 329(1-3):315-323, 2004. postscript

  3. Peter Jonsson and Andrei Krokhin: Complexity Classification in Qualitative Temporal Constraint Reasoning. Artificial Intelligence 160(1-2):35-51, 2004. postscript

  4. Vilhelm Dahllöf, Peter Jonsson, and Richard Beigel: Algorithms for Four Variants of the Exact Satisfiability Problem. Theoretical Computer Science 320(2-3):373-394, 2004. postscript / note

  5. Andrei Krokhin, Peter Jeavons, and Peter Jonsson: Constraint Satisfaction Problems on Intervals and Lengths. SIAM Journal on Discrete Mathematics 17(3):453-477, 2004. postscript

2003
  1. Mathias Broxvall and Peter Jonsson: Point Algebras for Temporal Reasoning: Algorithms and Complexity. Artificial Intelligence 149(2):179-220, 2003. postscript

  2. Andrei Krokhin, Peter Jeavons, and Peter Jonsson: Reasoning about Temporal Relations: The Tractable Subalgebras of Allen's Interval Algebra. Journal of the ACM 50(5):591-640, 2003. postscript

2002
  1. Mathias Broxvall, Peter Jonsson, and Jochen Renz: Disjunctions, Independence, Refinements. Artificial Intelligence 140(1-2):153-173, 2002. postscript

2000
  1. David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis: Building Tractable Disjunctive Constraints. Journal of the ACM 47(5):826-853, 2000. postscript

  2. Peter Jonsson: Boolean Constraint Satisfaction: Complexity Results for Optimization Problems with Arbitrary Weights. Theoretical Computer Science 244(1-2):189-203, 2000. postscript

  3. Peter Jonsson, Patrik Haslum, and Christer Bäckström: Towards Efficient Universal Planning - A Randomized Approach. Artificial Intelligence 117(1):1-29, 2000. postscript

1999
  1. Peter Jonsson: Strong Bounds on the Approximability of Two PSPACE-Hard Problems in Propositional Planning. Annals of Mathematics and Artificial Intelligence 26:133-147, 1999. postscript

  2. Peter Jonsson, Thomas Drakengren, and Christer Bäckström: Computational Complexity of Relating Time Points with Intervals. Artificial Intelligence 109(1-2):273-295, 1999. postscript

  3. Inger Klein, Peter Jonsson, and Christer Bäckström: Efficient Planning for a Miniature Assembly Line. Artificial Intelligence in Engineering 13(1):69-81, 1999.

1998
  1. Thomas Drakengren and Peter Jonsson: Reasoning About Set Constraints Applied to Tractable Inference in Intuitionistic Logic. Journal of Logic and Computation 8(6):855-875, 1998. postscript

  2. Thomas Drakengren and Peter Jonsson: A Complete Classification of Tractability in Allen's Algebra Relative to Subsets of Basic Relations. Artificial Intelligence 106(2):205-219, 1998. postscript

  3. Peter Jonsson: Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems. Information Processing Letters. 68(5):249-253, 1998. postscript

  4. Peter Jonsson and Christer Bäckström: Tractable Plan Existence Does Not Imply Tractable Plan Generation. Annals of Mathematics and Artificial Intelligence 22(3-4):281-296, 1998. postscript

  5. Peter Jonsson and Christer Bäckström: A Unifying Approach to Temporal Constraint Reasoning. Artificial Intelligence 102(1):143-155, 1998. postscript

  6. Peter Jonsson and Christer Bäckström: State-Variable Planning Under Structural Restrictions: Algorithms and Complexity. Artificial Intelligence 100(1-2):125-176, 1998. postscript

1997
  1. Peter Jonsson: A Nonapproximability Result for Finite Function Generation. Information Processing Letters 63:143-145, 1997. postscript

  2. Thomas Drakengren and Peter Jonsson: Twenty-One Large Tractable Subclasses of Allen's Algebra. Artificial Intelligence 93:297-319, 1997. postscript

  3. Thomas Drakengren and Peter Jonsson: Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time. Journal of Artificial Intelligence Research 7:25-45, 1997. paper

  4. Peter Jonsson and Thomas Drakengren: A Complete Classification of Tractability in RCC-5. Journal of Artificial Intelligence Research 6:211-221, 1997. paper