 | 2009 |
|---|
| 76 |       | Peter Jonsson,
Johan Thapper:
Approximability of the Maximum Solution Problem for Certain Families of Algebras.
CSR 2009: 215-226 |
| 75 | | Tommy Färnqvist,
Peter Jonsson,
Johan Thapper:
Approximability Distance in the Space of H-Colourability Problems.
CSR 2009: 92-104 |
| 74 | | Manuel Bodirsky,
Peter Jonsson,
Timo von Oertzen:
Semilinear Program Feasibility.
ICALP (2) 2009: 79-90 |
| 73 | | 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) |
| 72 | | 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) |
| 2008 |
|---|
| 71 | | Peter Jonsson,
Gustav Nordh:
Introduction to the Maximum SolutionProblem.
Complexity of Constraints 2008: 255-282 |
| 70 | | Tommy Färnqvist,
Peter Jonsson,
Johan Thapper:
Approximability Distance in the Space of H-Colourability Problems
CoRR abs/0802.0423: (2008) |
| 69 | | Vladimir G. Deineko,
Peter Jonsson,
Mikael Klasson,
Andrei A. Krokhin:
The approximability of MAX CSP with fixed-value constraints.
J. ACM 55(4): (2008) |
| 68 | | Peter Jonsson,
Andrei A. Krokhin:
Computational complexity of auditing finite attributes in statistical databases.
J. Comput. Syst. Sci. 74(5): 898-909 (2008) |
| 67 | | Peter Jonsson,
Fredrik Kuivinen,
Gustav Nordh:
MAX ONES Generalized to Larger Domains.
SIAM J. Comput. 38(1): 329-365 (2008) |
| 2007 |
|---|
| 66 | | Peter Jonsson,
Andrei A. Krokhin,
Fredrik Kuivinen:
Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems.
CSR 2007: 182-193 |
| 65 | | Tommy Färnqvist,
Peter Jonsson:
Bounded Tree-Width and CSP-Related Problems.
ISAAC 2007: 632-643 |
| 64 | | Peter Jonsson,
Gustav Nordh,
Johan Thapper:
The Maximum Solution Problem on Graphs.
MFCS 2007: 228-239 |
| 63 | | Peter Jonsson,
Andrei A. Krokhin,
Fredrik Kuivinen:
Hard constraint satisfaction problems have hard gaps at location 1
CoRR abs/0712.1532: (2007) |
| 62 | | Peter Jonsson,
Andrei A. Krokhin:
Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights.
J. Comput. Syst. Sci. 73(5): 691-702 (2007) |
| 2006 |
|---|
| 61 | | Peter Jonsson,
Fredrik Kuivinen,
Gustav Nordh:
Approximability of Integer Programming with Generalised Constraints.
CP 2006: 256-270 |
| 60 | | Peter Jonsson,
Gustav Nordh:
Generalised Integer Programming Based on Logically Defined Relations.
MFCS 2006: 549-560 |
| 59 | | Peter Jonsson,
Fredrik Kuivinen,
Gustav Nordh:
Approximability of Integer Programming with Generalised Constraints
CoRR abs/cs/0602047: (2006) |
| 58 | | Vladimir G. Deineko,
Peter Jonsson,
Mikael Klasson,
Andrei A. Krokhin:
The approximability of MAX CSP with fixed-value constraints
CoRR abs/cs/0602075: (2006) |
| 57 | | Peter Jonsson,
Mikael Klasson,
Andrei A. Krokhin:
The Approximability of Three-valued MAX CSP.
SIAM J. Comput. 35(6): 1329-1349 (2006) |
| 2005 |
|---|
| 56 |  | Peter Jonsson:
Adding clauses to poor man's logic (without increasing the complexity).
Journal of Applied Non-Classical Logics 15(3): 341-357 (2005) |
| 55 | | 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 |
|---|
| 54 | | Gustav Nordh,
Peter Jonsson:
The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups.
COCOON 2004: 370-379 |
| 53 | | Gustav Nordh,
Peter Jonsson:
An Algebraic Approach to the Complexity of Propositional Circumscription.
LICS 2004: 367-376 |
| 52 | | Peter Jonsson,
Andrei A. Krokhin:
Complexity classification in qualitative temporal constraint reasoning.
Artif. Intell. 160(1-2): 35-51 (2004) |
| 51 | | Peter Jonsson,
Mikael Klasson,
Andrei A. Krokhin:
The approximability of three-valued MAX CSP
CoRR abs/cs/0412042: (2004) |
| 50 | | Andrei A. Krokhin,
Peter Jeavons,
Peter Jonsson:
Constraint Satisfaction Problems on Intervals and Length.
SIAM J. Discrete Math. 17(3): 453-477 (2004) |
| 49 | | 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) |
| 48 | | Víctor Dalmau,
Peter Jonsson:
The complexity of counting homomorphisms seen from the other side.
Theor. Comput. Sci. 329(1-3): 315-323 (2004) |
| 47 | | Peter Jonsson,
Andrei A. Krokhin:
Recognizing frozen variables in constraint satisfaction problems.
Theor. Comput. Sci. 329(1-3): 93-113 (2004) |
| 2003 |
|---|
| 46 | | Ola Angelsmark,
Peter Jonsson:
Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems.
CP 2003: 81-95 |
| 45 | | Mathias Broxvall,
Peter Jonsson:
Point algebras for temporal reasoning: Algorithms and complexity.
Artif. Intell. 149(2): 179-220 (2003) |
| 44 | | Andrei A. Krokhin,
Peter Jonsson:
Recognizing Frozen Variables in Constraint Satisfaction Problems
Electronic Colloquium on Computational Complexity (ECCC)(062): (2003) |
| 43 | | 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) |
| 2002 |
|---|
| 42 | | Vilhelm Dahllöf,
Peter Jonsson,
Magnus Wahlström:
Counting Satisfying Assignments in 2-SAT and 3-SAT.
COCOON 2002: 535-543 |
| 41 | | Ola Angelsmark,
Peter Jonsson,
Svante Linusson,
Johan Thapper:
Determining the Number of Solutions to Binary CSP Instances.
CP 2002: 327-340 |
| 40 | | Ola Angelsmark,
Vilhelm Dahllöf,
Peter Jonsson:
Finite Domain Constraint Satisfaction Using Quantum Computation.
MFCS 2002: 93-103 |
| 39 | | Vilhelm Dahllöf,
Peter Jonsson:
An algorithm for counting maximum weighted independent sets and its applications.
SODA 2002: 292-298 |
| 38 | | Andrei A. Krokhin,
Peter Jeavons,
Peter Jonsson:
The Complexity of Constraints on Intervals and Lengths.
STACS 2002: 443-454 |
| 37 | | Andrei A. Krokhin,
Peter Jonsson:
Extending the Point Algebra into the Qualitative Algebra.
TIME 2002: 28-35 |
| 36 | | Mathias Broxvall,
Peter Jonsson,
Jochen Renz:
Disjunctions, independence, refinements.
Artif. Intell. 140(1/2): 153-173 (2002) |
| 2001 |
|---|
| 35 | | 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 |
| 34 | | Andrei A. Krokhin,
Peter Jeavons,
Peter Jonsson:
The complexity of constraints on intervals and lengths
Electronic Colloquium on Computational Complexity (ECCC)(077): (2001) |
| 2000 |
|---|
| 33 | | Mathias Broxvall,
Peter Jonsson:
Disjunctive Temporal Reasoning in Partially Ordered Models of Time.
AAAI/IAAI 2000: 464-469 |
| 32 | | Patrik Haslum,
Peter Jonsson:
Planning with Reduced Operator Sets.
AIPS 2000: 150-158 |
| 31 | | Mathias Broxvall,
Peter Jonsson,
Jochen Renz:
Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints.
CP 2000: 114-127 |
| 30 | | Ola Angelsmark,
Peter Jonsson:
Some Observations on Durations, Scheduling and Allen's Algebra.
CP 2000: 484-488 |
| 29 | | Peter Jonsson,
Patrik Haslum,
Christer Bäckström:
Towards efficient universal planning: A randomized approach.
Artif. Intell. 117(1): 1-29 (2000) |
| 28 | | David A. Cohen,
Peter Jeavons,
Peter Jonsson,
Manolis Koubarakis:
Building tractable disjunctive constraints.
J. ACM 47(5): 826-853 (2000) |
| 27 | | Peter Jonsson:
Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights.
Theor. Comput. Sci. 244(1-2): 189-203 (2000) |
| 1999 |
|---|
| 26 | | Marcus Bjäreland,
Peter Jonsson:
Exploiting Bipartiteness to Identify Yet Another Tractable Subclass of CSP.
CP 1999: 118-128 |
| 25 | | Mathias Broxvall,
Peter Jonsson:
Towards a Complete Classification of Tractability in Point Algebras for Nonlinear Time.
CP 1999: 129-143 |
| 24 | | Patrik Haslum,
Peter Jonsson:
Some Results on the Complexity of Planning with Incomplete Information.
ECP 1999: 308-318 |
| 23 | | Inger Klein,
Peter Jonsson,
Christer Bäckström:
Efficient planning for a miniature assembly line.
AI in Engineering 13(1): 69-81 (1999) |
| 22 | | 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) |
| 21 | | Peter Jonsson,
Thomas Drakengren,
Christer Bäckström:
Computational Complexity of Relating Time Points with Intervals.
Artif. Intell. 109(1-2): 273-295 (1999) |
| 20 | | Peter Jonsson,
Paolo Liberatore:
On the Complexity of Finding Satisfiable Subinstances in Constraint Satisfaction
Electronic Colloquium on Computational Complexity (ECCC) 6(38): (1999) |
| 1998 |
|---|
| 19 | | 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) |
| 18 | | Peter Jonsson,
Christer Bäckström:
State-Variable Planning Under Structural Restrictions: Algorithms and Complexity.
Artif. Intell. 100(1-2): 125-176 (1998) |
| 17 | | Peter Jonsson,
Christer Bäckström:
A Unifying Approach to Temporal Constraint Reasoning.
Artif. Intell. 102(1): 143-155 (1998) |
| 16 | | 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) |
| 15 | | Peter Jonsson:
Near-Optimal Nonapproximability Results for Some NPO PB-Complete Problems.
Inf. Process. Lett. 68(5): 249-253 (1998) |
| 14 | | Thomas Drakengren,
Peter Jonsson:
Reasoning About Set Constraints Applied to Tractable Inference in Intuitionistic Logic.
J. Log. Comput. 8(6): 855-875 (1998) |
| 1997 |
|---|
| 13 | | Thomas Drakengren,
Peter Jonsson:
Towards a Complete Classification of Tractability in Allen's Algebra.
IJCAI 1997: 1466-1475 |
| 12 | | Thomas Drakengren,
Peter Jonsson:
Twenty-One Large Tractable Subclasses of Allen's Algebra.
Artif. Intell. 93: 297-319 (1997) |
| 11 | | Peter Jonsson,
Thomas Drakengren:
A Complete Classification of Tractability in RCC-5
CoRR cs.AI/9706102: (1997) |
| 10 | | Thomas Drakengren,
Peter Jonsson:
Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time
CoRR cs.AI/9707102: (1997) |
| 9 | | Peter Jonsson:
A Nonapproximability Result for Finite Function Generation.
Inf. Process. Lett. 63(3): 143-145 (1997) |
| 8 | | Peter Jonsson,
Thomas Drakengren:
A Complete Classification of Tractability in RCC-5.
J. Artif. Intell. Res. (JAIR) 6: 211-221 (1997) |
| 7 | | Thomas Drakengren,
Peter Jonsson:
Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time.
J. Artif. Intell. Res. (JAIR) 7: 25-45 (1997) |
| 1996 |
|---|
| 6 | | Thomas Drakengren,
Peter Jonsson:
Maximal Tractable Subclasses of Allen's Interval Algebra: Preliminary Report.
AAAI/IAAI, Vol. 1 1996: 389-394 |
| 5 | | Peter Jonsson,
Christer Bäckström:
On the Size of Reactive Plans.
AAAI/IAAI, Vol. 2 1996: 1182-1187 |
| 4 | | Peter Jonsson,
Christer Bäckström:
A Linear-Programming Approach to Temporal Reasoning.
AAAI/IAAI, Vol. 2 1996: 1235-1240 |
| 3 | | Peter Jonsson,
Thomas Drakengren,
Christer Bäckström:
Tractable Subclasses of the Point-Interval Algebra: A Complete Classification.
KR 1996: 352-363 |
| 1995 |
|---|
| 2 | | Christer Bäckström,
Peter Jonsson:
Planning with Abstraction Hierarchies can be Exponentially Less Efficient.
IJCAI 1995: 1599-1605 |
| 1994 |
|---|
| 1 | | Peter Jonsson,
Christer Bäckström:
Tractable Planning with State Variables by Exploiting Structural Restrictions.
AAAI 1994: 998-1003 |
