Johan Thapper

Publication Activity (10 Years)

Years Active: 2000-2018
Publications (10 Years): 18

Top Topics

Hypertree Decomposition

Linear Programming

Constraint Satisfaction

Top Venues

SIAM J. Comput.

J. Comput. Syst. Sci.

Publications

Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Abdelhakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, N. Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
Tropical dominating sets in vertex-coloured graphs. J. Discrete Algorithms 48 (2018)
Johan Thapper, Stanislav Zivný
The Limits of SDP Relaxations for General-Valued CSPs. ACM Trans. Comput. Theory 10 (3) (2018)
Peter Jonsson, Johan Thapper
Tractability conditions for numeric CSPs. Theor. Comput. Sci. 715 (2018)
Johan Thapper, Stanislav Zivný
The Power of Sherali-Adams Relaxations for General-Valued CSPs. SIAM J. Comput. 46 (4) (2017)
Johan Thapper, Stanislav Zivný
The limits of SDP relaxations for general-valued CSPs. LICS (2017)
Peter Jonsson, Johan Thapper
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals. J. Comput. Syst. Sci. 82 (5) (2016)
Johan Thapper, Stanislav Zivný
The limits of SDP relaxations for general-valued CSPs. CoRR (2016)
Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
Tropical Dominating Sets in Vertex-Coloured Graphs. WALCOM (2016)
Johan Thapper, Stanislav Zivný
The Complexity of Finite-Valued CSPs. J. ACM 63 (4) (2016)
Johan Thapper, Stanislav Zivný
The power of Sherali-Adams relaxations for general-valued CSPs. CoRR (2016)
Vladimir Kolmogorov, Johan Thapper, Stanislav Zivný
The Power of Linear Programming for General-Valued CSPs. SIAM J. Comput. 44 (1) (2015)
Johan Thapper, Stanislav Zivný
Necessary Conditions for Tractability of Valued CSPs. SIAM J. Discret. Math. 29 (4) (2015)
Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper
An Approximability-related Parameter on Graphs - Properties and Applications. Discret. Math. Theor. Comput. Sci. 17 (1) (2015)
Peter Jonsson, Johan Thapper
Constraint Satisfaction and Semilinear Expansions of Addition over the Rationals and the Reals. CoRR (2015)
Jean-Alexandre Anglès d'Auriac, Csilla Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, N. Narayanan, Laurent Rosaz, Johan Thapper, Zsolt Tuza
Tropical Dominating Sets in Vertex-Coloured Graphs. CoRR (2015)
Johan Thapper, Stanislav Zivný
Necessary conditions for tractability of valued CSPs. CoRR (2015)
Johan Thapper, Stanislav Zivný
Sherali-Adams Relaxations for Valued CSPs. ICALP (1) (2015)
Johan Thapper, Stanislav Zivný
Sherali-Adams relaxations for valued CSPs. CoRR (2015)
Peter Jonsson, Johan Thapper
Affine Consistency and the Complexity of Semilinear Constraints. MFCS (2) (2014)
Manuel Bodirsky, H. Dugald Macpherson, Johan Thapper
Constraint satisfaction tractability from semi-lattice operations on infinite sets. ACM Trans. Comput. Log. 14 (4) (2013)
Johan Thapper, Stanislav Zivný
The complexity of finite-valued CSPs. STOC (2013)
Vladimir Kolmogorov, Johan Thapper, Stanislav Zivný
The power of linear programming for general-valued CSPs. CoRR (2013)
Johan Thapper, Stanislav Zivný
The Power of Linear Programming for Valued CSPs. FOCS (2012)
Johan Thapper, Stanislav Zivný
The complexity of finite-valued CSPs CoRR (2012)
Johan Thapper, Stanislav Zivný
The Power of Linear Programming for Valued CSPs CoRR (2012)
Peter Jonsson, Fredrik Kuivinen, Johan Thapper
Min CSP on Four Elements: Moving Beyond Submodularity CoRR (2011)
Manuel Bodirsky, Dugald Macpherson, Johan Thapper
Constraint Satisfaction Tractability from Semi-lattice Operations on Infinite Sets CoRR (2011)
Peter Jonsson, Fredrik Kuivinen, Johan Thapper
Min CSP on Four Elements: Moving beyond Submodularity. CP (2011)
Peter Jonsson, Johan Thapper
Approximating integer programs with positive right-hand sides. Inf. Process. Lett. 110 (10) (2010)
Peter Jonsson, Johan Thapper
Approximability of the Maximum Solution Problem for Certain Families of Algebras. CSR (2009)
Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper
Graph Homomorphisms, Circular Colouring, and Fractional Covering by H-cuts CoRR (2009)
Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper
Properties of an Approximability-related Parameter on Circular Complete Graphs. Electron. Notes Discret. Math. 35 (2009)
Tommy Färnqvist, Peter Jonsson, Johan Thapper
-Colourability Problems. CSR (2009)
Tommy Färnqvist, Peter Jonsson, Johan Thapper
Approximability Distance in the Space of H-Colourability Problems CoRR (2008)
Peter Jonsson, Gustav Nordh, Johan Thapper
The Maximum Solution Problem on Graphs. MFCS (2007)
Ola Angelsmark, Johan Thapper
Partitioning Based Algorithms for Some Colouring Problems. CSCLP (2005)
Ola Angelsmark, Johan Thapper
A Microstructure Based Approach to Constraint Satisfaction Optimisation Problems. FLAIRS Conference (2005)
Ola Angelsmark, Johan Thapper
Algorithms for the Maximum Hamming Distance Problem. CSCLP (2004)
Ola Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper
Determining the Number of Solutions to Binary CSP Instances. CP (2002)
Anneli Dahlström, Fredrik Heintz, Martin Jacobsson, Johan Thapper, Martin Öberg
The NOAI Team Description. RoboCup (2000)