dblp.uni-trier.dewww.uni-trier.de

Peter Jonsson Vis

List of publications from the DBLP Bibliography Server - FAQ
Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo
Home Page

*2009
76EEPeter Jonsson, Johan Thapper: Approximability of the Maximum Solution Problem for Certain Families of Algebras. CSR 2009: 215-226
75EETommy Färnqvist, Peter Jonsson, Johan Thapper: Approximability Distance in the Space of H-Colourability Problems. CSR 2009: 92-104
74EEManuel Bodirsky, Peter Jonsson, Timo von Oertzen: Semilinear Program Feasibility. ICALP (2) 2009: 79-90
73EERobert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper: Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts CoRR abs/0904.4600: (2009)
72EEPeter 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
71EEPeter Jonsson, Gustav Nordh: Introduction to the Maximum SolutionProblem. Complexity of Constraints 2008: 255-282
70EETommy Färnqvist, Peter Jonsson, Johan Thapper: Approximability Distance in the Space of H-Colourability Problems CoRR abs/0802.0423: (2008)
69EEVladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of MAX CSP with fixed-value constraints. J. ACM 55(4): (2008)
68EEPeter Jonsson, Andrei A. Krokhin: Computational complexity of auditing finite attributes in statistical databases. J. Comput. Syst. Sci. 74(5): 898-909 (2008)
67EEPeter Jonsson, Fredrik Kuivinen, Gustav Nordh: MAX ONES Generalized to Larger Domains. SIAM J. Comput. 38(1): 329-365 (2008)
2007
66EEPeter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems. CSR 2007: 182-193
65EETommy Färnqvist, Peter Jonsson: Bounded Tree-Width and CSP-Related Problems. ISAAC 2007: 632-643
64EEPeter Jonsson, Gustav Nordh, Johan Thapper: The Maximum Solution Problem on Graphs. MFCS 2007: 228-239
63EEPeter Jonsson, Andrei A. Krokhin, Fredrik Kuivinen: Hard constraint satisfaction problems have hard gaps at location 1 CoRR abs/0712.1532: (2007)
62EEPeter Jonsson, Andrei A. Krokhin: Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights. J. Comput. Syst. Sci. 73(5): 691-702 (2007)
2006
61EEPeter Jonsson, Fredrik Kuivinen, Gustav Nordh: Approximability of Integer Programming with Generalised Constraints. CP 2006: 256-270
60EEPeter Jonsson, Gustav Nordh: Generalised Integer Programming Based on Logically Defined Relations. MFCS 2006: 549-560
59EEPeter Jonsson, Fredrik Kuivinen, Gustav Nordh: Approximability of Integer Programming with Generalised Constraints CoRR abs/cs/0602047: (2006)
58EEVladimir G. Deineko, Peter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of MAX CSP with fixed-value constraints CoRR abs/cs/0602075: (2006)
57EEPeter 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)
55EEVilhelm Dahllöf, Peter Jonsson, Magnus Wahlström: Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332(1-3): 265-291 (2005)
2004
54EEGustav Nordh, Peter Jonsson: The Complexity of Counting Solutions to Systems of Equations over Finite Semigroups. COCOON 2004: 370-379
53EEGustav Nordh, Peter Jonsson: An Algebraic Approach to the Complexity of Propositional Circumscription. LICS 2004: 367-376
52EEPeter Jonsson, Andrei A. Krokhin: Complexity classification in qualitative temporal constraint reasoning. Artif. Intell. 160(1-2): 35-51 (2004)
51EEPeter Jonsson, Mikael Klasson, Andrei A. Krokhin: The approximability of three-valued MAX CSP CoRR abs/cs/0412042: (2004)
50EEAndrei A. Krokhin, Peter Jeavons, Peter Jonsson: Constraint Satisfaction Problems on Intervals and Length. SIAM J. Discrete Math. 17(3): 453-477 (2004)
49EEVilhelm Dahllöf, Peter Jonsson, Richard Beigel: Algorithms for four variants of the exact satisfiability problem. Theor. Comput. Sci. 320(2-3): 373-394 (2004)
48EEVíctor Dalmau, Peter Jonsson: The complexity of counting homomorphisms seen from the other side. Theor. Comput. Sci. 329(1-3): 315-323 (2004)
47EEPeter Jonsson, Andrei A. Krokhin: Recognizing frozen variables in constraint satisfaction problems. Theor. Comput. Sci. 329(1-3): 93-113 (2004)
2003
46EEOla Angelsmark, Peter Jonsson: Improved Algorithms for Counting Solutions in Constraint Satisfaction Problems. CP 2003: 81-95
45EEMathias Broxvall, Peter Jonsson: Point algebras for temporal reasoning: Algorithms and complexity. Artif. Intell. 149(2): 179-220 (2003)
44EEAndrei A. Krokhin, Peter Jonsson: Recognizing Frozen Variables in Constraint Satisfaction Problems Electronic Colloquium on Computational Complexity (ECCC)(062): (2003)
43EEAndrei 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
42EEVilhelm Dahllöf, Peter Jonsson, Magnus Wahlström: Counting Satisfying Assignments in 2-SAT and 3-SAT. COCOON 2002: 535-543
41EEOla Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper: Determining the Number of Solutions to Binary CSP Instances. CP 2002: 327-340
40EEOla Angelsmark, Vilhelm Dahllöf, Peter Jonsson: Finite Domain Constraint Satisfaction Using Quantum Computation. MFCS 2002: 93-103
39EEVilhelm Dahllöf, Peter Jonsson: An algorithm for counting maximum weighted independent sets and its applications. SODA 2002: 292-298
38EEAndrei A. Krokhin, Peter Jeavons, Peter Jonsson: The Complexity of Constraints on Intervals and Lengths. STACS 2002: 443-454
37EEAndrei A. Krokhin, Peter Jonsson: Extending the Point Algebra into the Qualitative Algebra. TIME 2002: 28-35
36EEMathias 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
34EEAndrei 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
31EEMathias Broxvall, Peter Jonsson, Jochen Renz: Refinements and Independence: A Simple Method for Identifying Tractable Disjunctive Constraints. CP 2000: 114-127
30EEOla Angelsmark, Peter Jonsson: Some Observations on Durations, Scheduling and Allen's Algebra. CP 2000: 484-488
29EEPeter Jonsson, Patrik Haslum, Christer Bäckström: Towards efficient universal planning: A randomized approach. Artif. Intell. 117(1): 1-29 (2000)
28EEDavid A. Cohen, Peter Jeavons, Peter Jonsson, Manolis Koubarakis: Building tractable disjunctive constraints. J. ACM 47(5): 826-853 (2000)
27EEPeter 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
23EEInger 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)
21EEPeter Jonsson, Thomas Drakengren, Christer Bäckström: Computational Complexity of Relating Time Points with Intervals. Artif. Intell. 109(1-2): 273-295 (1999)
20EEPeter 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)
18EEPeter Jonsson, Christer Bäckström: State-Variable Planning Under Structural Restrictions: Algorithms and Complexity. Artif. Intell. 100(1-2): 125-176 (1998)
17EEPeter Jonsson, Christer Bäckström: A Unifying Approach to Temporal Constraint Reasoning. Artif. Intell. 102(1): 143-155 (1998)
16EEThomas 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)
15EEPeter 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
12EEThomas Drakengren, Peter Jonsson: Twenty-One Large Tractable Subclasses of Allen's Algebra. Artif. Intell. 93: 297-319 (1997)
11EEPeter Jonsson, Thomas Drakengren: A Complete Classification of Tractability in RCC-5 CoRR cs.AI/9706102: (1997)
10EEThomas Drakengren, Peter Jonsson: Eight Maximal Tractable Subclasses of Allen's Algebra with Metric Time CoRR cs.AI/9707102: (1997)
9EEPeter 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

Coauthor Index

1Ola Angelsmark [30] [40] [41] [46]
2Christer Bäckström [1] [2] [3] [4] [5] [17] [18] [19] [21] [23] [29]
3Richard Beigel [49]
4Marcus Bjäreland [26]
5Manuel Bodirsky [74]
6Mathias Broxvall [25] [31] [33] [36] [45]
7David A. Cohen [28]
8Vilhelm Dahllöf [39] [40] [42] [49] [55]
9Víctor Dalmau [48]
10Vladimir G. Deineko [58] [69]
11Thomas Drakengren [3] [6] [7] [8] [10] [11] [12] [13] [14] [16] [21]
12Robert Engström [73]
13Tommy Färnqvist [65] [70] [73] [75]
14Patrik Haslum [24] [29] [32]
15Peter Jeavons (Peter G. Jeavons) [28] [34] [35] [38] [43] [50]
16Mikael Klasson [51] [57] [58] [69]
17Inger Klein [23]
18Manolis Koubarakis [28]
19Andrei A. Krokhin [34] [35] [37] [38] [43] [44] [47] [50] [51] [52] [57] [58] [62] [63] [66] [68] [69] [72]
20Fredrik Kuivinen [59] [61] [63] [66] [67] [72]
21Paolo Liberatore [20]
22Svante Linusson [41]
23Gustav Nordh [53] [54] [59] [60] [61] [64] [67] [71]
24Timo von Oertzen [74]
25Jochen Renz [31] [36]
26Johan Thapper [41] [64] [70] [73] [75] [76]
27Magnus Wahlström [42] [55]

Colors in the list of coauthors

Copyright © Tue Nov 3 08:52:44 2009 by Michael Ley (ley@uni-trier.de)