An approximability-related parameter on graphs―-properties and applications

Autor: Robert Engström, Tommy Färnqvist, Peter Jonsson, Johan Thapper

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol Vol. 17 no. 1, Iss Graph Theory (2015)

Graph Theory

Externí odkaz: https://doaj.org/article/5372346a63d94b86823d9b69948a989f

The power of Sherali-Adams relaxations for general-valued CSPs

Autor: Johan Thapper, Stanislav Živný

Publikováno v: SIAM Journal on Computing
SIAM Journal on Computing, Society for Industrial and Applied Mathematics, 2017, 46 (4), pp.1241-1279. ⟨10.1137/16M1079245⟩

We give a precise algebraic characterisation of the power of Sherali-Adams relaxations for solvability of valued constraint satisfaction problems to optimality. The condition is that of bounded width which has already been shown to capture the power

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::13d62ba61f8898ad9f46f0792a96565b
http://ora.ox.ac.uk/objects/uuid:

The limits of SDP relaxations for general-valued CSPs

Autor: Stanislav Živný, Johan Thapper

Publikováno v: ACM Transactions on Computation Theory
ACM Transactions on Computation Theory, ACM, 2018, 10 (3), pp.1-22. ⟨10.1145/3201777⟩
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2017, Reykjavik, Iceland. ⟨10.1109/LICS.2017.8005087⟩
2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Jun 2017, Reykjavik, Iceland. IEEE, 〈10.1109/LICS.2017.8005087〉

It has been shown that for a general-valued constraint language $\Gamma$ the following statements are equivalent: (1) any instance of $\operatorname{VCSP}(\Gamma)$ can be solved to optimality using a constant level of the Sherali-Adams LP hierarchy;

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5b9e396d57586985f4e3fe12cca7f283

Tropical Dominating Sets in Vertex-Coloured Graphs

Autor: Leandro Montero, Zsolt Tuza, Csilia Bujtás, Hakim El Maftouhi, Laurent Rosaz, N. Narayanan, Johan Thapper, Marek Karpinski, Yannis Manoussakis, Jean Alexandre Anglés D’Auriac

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783319301389
WALCOM

Given a vertex-coloured graph, a dominating set is said to be tropical if every colour of the graph appears at least once in the set. Here, we study minimum tropical dominating sets from structural and algorithmic points of view. First, we prove that

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::635d51f5a2c1410a50d34412c72295ce
https://doi.org/10.1007/978-3-319-30139-6_2

Properties of an Approximability-related Parameter on Circular Complete Graphs

Autor: Robert Engström, Johan Thapper, Tommy Färnqvist, Peter Jonsson

Publikováno v: Electronic Notes in Discrete Mathematics. 35:115-120

The instances of the Weighted Maximum H-Colourable Subgraph problem ( Max H- Col ) are edge-weighted graphs G and the objective is to find a subgraph of G that has maximal total edge weight, under the condition that the subgraph has a homomorphism to

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::1823ebdc0c85d623490b95c6cc9033f9
https://doi.org/10.1016/j.endm.2009.11.020