Please note: This is a beta version of the new dblp website.
You can find the classic dblp view of this page here.
You can find the classic dblp view of this page here.
Peter Jonsson
2010 – today
- 2013
[j40]Peter Jonsson, Tomas Lööw: Computational complexity of linear constraints over the integers. Artif. Intell. 195: 44-62 (2013)- [c44]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider: Parameterized Complexity and Kernel Bounds for Hard Planning Problems. CIAC 2013: 13-24
- [c43]Peter Jonsson, Victor Lagerkvist, Gustav Nordh, Bruno Zanuttini: Complexity of SAT Problems, Clone Theory and the Exponential Time Hypothesis. SODA 2013: 1264-1277
- 2012
- [j39]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen: Essential Convexity and Complexity of Semi-Algebraic Constraints. Logical Methods in Computer Science 8(4) (2012)
- [j38]Christer Bäckström, Peter Jonsson: Algorithms and Limits for Compact Plan Representations. J. Artif. Intell. Res. (JAIR) 44: 141-177 (2012)
- [j37]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen: Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfaction. J. Log. Comput. 22(3): 643-660 (2012)
- [c42]Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider: The Complexity of Planning Revisited - A Parameterized Analysis. AAAI 2012
- [c41]Christer Bäckström, Anders Jonsson, Peter Jonsson: Macros, Reactive Plans and Compact Representations. ECAI 2012: 85-90
- [c40]Christer Bäckström, Anders Jonsson, Peter Jonsson: From Macro Plans to Automata Plans. ECAI 2012: 91-96
- [c39]Christer Bäckström, Peter Jonsson: Abstracting Abstraction in Search with Applications to Planning. KR 2012
- [c38]Christer Bäckström, Peter Jonsson: Abstracting Abstraction in Search II: Complexity Analysis. SOCS 2012
- [i15]Christer Bäckström, Yue Chen, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider: The Complexity of Planning Revisited - A Parameterized Analysis. CoRR abs/1208.2566 (2012)
- [i14]Christer Bäckström, Peter Jonsson, Sebastian Ordyniak, Stefan Szeider: Parameterized Complexity and Kernel Bounds for Hard Planning Problems. CoRR abs/1211.0479 (2012)
- 2011
- [c37]
- [c36]Peter Jonsson, Fredrik Kuivinen, Johan Thapper: Min CSP on Four Elements: Moving beyond Submodularity. CP 2011: 438-453
- [c35]
- [c34]Christer Bäckström, Peter Jonsson: All PSPACE-Complete Planning Problems Are Equal but Some Are More Equal than Others. SOCS 2011
- [i13]Peter Jonsson, Fredrik Kuivinen, Johan Thapper: Min CSP on Four Elements: Moving Beyond Submodularity. CoRR abs/1102.2880 (2011)
- 2010
- [j36]Peter Jonsson, Johan Thapper: Approximating integer programs with positive right-hand sides. Inf. Process. Lett. 110(10): 351-355 (2010)
- [j35]Peter Jonsson, Gustav Nordh: Approximability of Clausal Constraints. Theory Comput. Syst. 46(2): 370-395 (2010)
- [j34]Tomás Feder, Pavol Hell, Peter Jonsson, Andrei A. Krokhin, Gustav Nordh: Retractions to Pseudoforests. SIAM J. Discrete Math. 24(1): 101-112 (2010)
- [i12]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen: Horn versus full first-order: complexity dichotomies in algebraic constraint satisfaction. CoRR abs/1005.1141 (2010)
2000 – 2009
- 2009
- [j33]Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper: Properties of an Approximability-related Parameter on Circular Complete Graphs. Electronic Notes in Discrete Mathematics 35: 115-120 (2009)
- [j32]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1. Theor. Comput. Sci. 410(38-40): 3856-3874 (2009)
- [c33]Tommy Färnqvist, Peter Jonsson, Johan Thapper: Approximability Distance in the Space of H-Colourability Problems. CSR 2009: 92-104
- [c32]Peter Jonsson, Johan Thapper: Approximability of the Maximum Solution Problem for Certain Families of Algebras. CSR 2009: 215-226
- [c31]Manuel Bodirsky, Peter Jonsson, Timo von Oertzen: Semilinear Program Feasibility. ICALP (2) 2009: 79-90
- [i11]Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper: Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts. CoRR abs/0904.4600 (2009)
- 2008
- [j31]Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of MAX CSP with fixed-value constraints. J. ACM 55(4) (2008)
- [j30]Peter Jonsson, Andrei A. Krokhin: Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74(5): 898-909 (2008)
- [j29]Peter Jonsson, Fredrik Kuivinen, Gustav Nordh: MAX ONES Generalized to Larger Domains. SIAM J. Comput. 38(1): 329-365 (2008)
- [c30]Peter Jonsson, Gustav Nordh: Introduction to the Maximum SolutionProblem. Complexity of Constraints 2008: 255-282
- [i10]Tommy Färnqvist, Peter Jonsson, Johan Thapper: Approximability Distance in the Space of H-Colourability Problems. CoRR abs/0802.0423 (2008)
- 2007
- [j28]Peter Jonsson, Andrei A. Krokhin: Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. 73(5): 691-702 (2007)
- [c29]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR 2007: 182-193
- [c28]
- [c27]Peter Jonsson, Gustav Nordh, Johan Thapper: The Maximum Solution Problem on Graphs. MFCS 2007: 228-239
- [i9]Peter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1. CoRR abs/0712.1532 (2007)
- 2006
- [j27]Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The Approximability of Three-valued MAX CSP. SIAM J. Comput. 35(6): 1329-1349 (2006)
- [c26]Peter Jonsson, Fredrik Kuivinen, Gustav Nordh: Approximability of Integer Programming with Generalised Constraints. CP 2006: 256-270
- [c25]Peter Jonsson, Gustav Nordh: Generalised Integer Programming Based on Logically Defined Relations. MFCS 2006: 549-560
- [i8]Peter Jonsson, Fredrik Kuivinen, Gustav Nordh: Approximability of Integer Programming with Generalised Constraints. CoRR abs/cs/0602047 (2006)
- [i7]Vladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of MAX CSP with fixed-value constraints. CoRR abs/cs/0602075 (2006)
- 2005
- [j26]Peter Jonsson: Adding clauses to poor man's logic (without increasing the complexity). Journal of Applied Non-Classical Logics 15(3): 341-357 (2005)
- [j25]Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström: Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332(1-3): 265-291 (2005)
- 2004
- [j24]Peter Jonsson, Andrei A. Krokhin: Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160(1-2): 35-51 (2004)
- [j23]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discrete Math. 17(3): 453-477 (2004)
- [j22]Vilhelm Dahllöf, Peter Jonsson, Richard Beigel: Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. 320(2-3): 373-394 (2004)
- [j21]Peter Jonsson, Andrei A. Krokhin: Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329(1-3): 93-113 (2004)
- [j20]Víctor Dalmau, Peter Jonsson: The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1-3): 315-323 (2004)
- [c24]Gustav Nordh, Peter Jonsson: The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups. COCOON 2004: 370-379
- [c23]Gustav Nordh, Peter Jonsson: An Algebraic Approach to the Complexity of Propositional Circumscription. LICS 2004: 367-376
- [i6]Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of three-valued MAX CSP. CoRR abs/cs/0412042 (2004)
- 2003
- [j19]Mathias Broxvall, Peter Jonsson: Point algebras for temporal reasoning: Algorithms and complexity. Artif. Intell. 149(2): 179-220 (2003)
- [j18]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. J. ACM 50(5): 591-640 (2003)
- [c22]Ola Angelsmark, Peter Jonsson: Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems. CP 2003: 81-95
- [i5]Andrei A. Krokhin, Peter Jonsson: Recognizing Frozen Variables in Constraint Satisfaction Problems. Electronic Colloquium on Computational Complexity (ECCC)(062) (2003)
- 2002
- [j17]Mathias Broxvall, Peter Jonsson, Jochen Renz: Disjunctions, independence, refinements. Artif. Intell. 140(1/2): 153-173 (2002)
- [c21]Vilhelm Dahllöf, Peter Jonsson, Magnus Wahlström: Counting Satisfying Assignments in 2-SAT and 3-SAT. COCOON 2002: 535-543
- [c20]Ola Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper: Determining the Number of Solutions to Binary CSP Instances. CP 2002: 327-340
- [c19]Ola Angelsmark, Vilhelm Dahllöf, Peter Jonsson: Finite Domain Constraint Satisfaction Using Quantum Computation. MFCS 2002: 93-103
- [c18]Vilhelm Dahllöf, Peter Jonsson: An algorithm for counting maximum weighted independent sets and its applications. SODA 2002: 292-298
- [c17]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: The Complexity of Constraints on Intervals and Lengths. STACS 2002: 443-454
- [c16]Andrei A. Krokhin, Peter Jonsson: Extending the Point Algebra into the Qualitative Algebra. TIME 2002: 28-35
- 2001
- [c15]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: A Complete Classification of Complexity in Allens Algebra in the Presence of a Non-Trivial Basic Relation. IJCAI 2001: 83-88
- [i4]Andrei A. Krokhin, Peter Jeavons, Peter Jonsson: The complexity of constraints on intervals and lengths. Electronic Colloquium on Computational Complexity (ECCC)(077) (2001)
- 2000
- [j16]Peter Jonsson, Patrik Haslum, Christer Bäckström: Towards efficient universal planning: A randomized approach. Artif. Intell. 117(1): 1-29 (2000)
- [j15]David A. Cohen, Peter Jeavons, Peter Jonsson, Manolis Koubarakis: Building tractable disjunctive constraints. J. ACM 47(5): 826-853 (2000)
- [j14]Peter Jonsson: Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights. Theor. Comput. Sci. 244(1-2): 189-203 (2000)
- [c14]Mathias Broxvall, Peter Jonsson: Disjunctive Temporal Reasoning in Partially Ordered Models of Time. AAAI/IAAI 2000: 464-469
- [c13]
- [c12]Mathias Broxvall, Peter Jonsson, Jochen Renz: Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints. CP 2000: 114-127
- [c11]Ola Angelsmark, Peter Jonsson: Some Observations on Durations, Scheduling and Allen's Algebra. CP 2000: 484-488
1990 – 1999
- 1999
- [j13]Inger Klein, Peter Jonsson, Christer Bäckström: Efficient planning for a miniature assembly line. AI in Engineering 13(1): 69-81 (1999)
- [j12]Peter Jonsson, Thomas Drakengren, Christer Bäckström: Computational Complexity of Relating Time Points with Intervals. Artif. Intell. 109(1-2): 273-295 (1999)
- [j11]Peter Jonsson: Strong bounds on the approximability of two Pspace-hard problems in propositional planning. Ann. Math. Artif. Intell. 26(1-4): 133-147 (1999)
- [c10]Marcus Bjäreland, Peter Jonsson: Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP. CP 1999: 118-128
- [c9]Mathias Broxvall, Peter Jonsson: Towards a Complete Classification of Tractability in Point Algebras for Nonlinear Time. CP 1999: 129-143
- [c8]Patrik Haslum, Peter Jonsson: Some Results on the Complexity of Planning with Incomplete Information. ECP 1999: 308-318
- [i3]Peter Jonsson, Paolo Liberatore: On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction. Electronic Colloquium on Computational Complexity (ECCC) 6(38) (1999)
- 1998
- [j10]Peter Jonsson, Christer Bäckström: State-Variable Planning Under Structural Restrictions: Algorithms and Complexity. Artif. Intell. 100(1-2): 125-176 (1998)
- [j9]Peter Jonsson, Christer Bäckström: A Unifying Approach to Temporal Constraint Reasoning. Artif. Intell. 102(1): 143-155 (1998)
- [j8]Thomas Drakengren, Peter Jonsson: A Complete Classification of Tractability in Allen's Algebra Relative to Subsets of Basic Relations. Artif. Intell. 106(2): 205-219 (1998)
- [j7]Peter Jonsson, Christer Bäckström: Tractable Plan Existence Does Not Imply Tractable Plan Generation. Ann. Math. Artif. Intell. 22(3-4): 281-296 (1998)
- [j6]Peter Jonsson: Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems. Inf. Process. Lett. 68(5): 249-253 (1998)
- [j5]Thomas Drakengren, Peter Jonsson: Reasoning About Set Constraints Applied to Tractable Inference in Intuitionistic Logic. J. Log. Comput. 8(6): 855-875 (1998)
- 1997
- [j4]Thomas Drakengren, Peter Jonsson: Twenty-One Large Tractable Subclasses of Allen's Algebra. Artif. Intell. 93: 297-319 (1997)
- [j3]Peter Jonsson: A Nonapproximability Result for Finite Function Generation. Inf. Process. Lett. 63(3): 143-145 (1997)
- [j2]Peter Jonsson, Thomas Drakengren: A Complete Classification of Tractability in RCC-5. J. Artif. Intell. Res. (JAIR) 6: 211-221 (1997)
- [j1]Thomas Drakengren, Peter Jonsson: Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time. J. Artif. Intell. Res. (JAIR) 7: 25-45 (1997)
- [c7]Thomas Drakengren, Peter Jonsson: Towards a Complete Classification of Tractability in Allen's Algebra. IJCAI 1997: 1466-1475
- [i2]Peter Jonsson, Thomas Drakengren: A Complete Classification of Tractability in RCC-5. CoRR cs.AI/9706102 (1997)
- [i1]Thomas Drakengren, Peter Jonsson: Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time. CoRR cs.AI/9707102 (1997)
- 1996
- [c6]Thomas Drakengren, Peter Jonsson: Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report. AAAI/IAAI, Vol. 1 1996: 389-394
- [c5]
- [c4]Peter Jonsson, Christer Bäckström: A Linear-Programming Approach to Temporal Reasoning. AAAI/IAAI, Vol. 2 1996: 1235-1240
- [c3]Peter Jonsson, Thomas Drakengren, Christer Bäckström: Tractable Subclasses of the Point-Interval Algebra: A Complete Classification. KR 1996: 352-363
- 1995
- [c2]Christer Bäckström, Peter Jonsson: Planning with Abstraction Hierarchies can be Exponentially Less Efficient. IJCAI 1995: 1599-1605
- 1994
- [c1]Peter Jonsson, Christer Bäckström: Tractable Planning with State Variables by Exploiting Structural Restrictions. AAAI 1994: 998-1003
Coauthor Index
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-05-23 22:19 CEST by the dblp team