Zobrazeno 1 - 9
of 9
pro vyhledávání: '"Barsukov, Alexey"'
Guarded Monotone Strict NP (GMSNP) extends Monotone Monadic Strict NP (MMSNP) by guarded existentially quantified predicates of arbitrary arities. We prove that the containment problem for GMSNP is decidable, hereby settling an open question of Bienv
Externí odkaz:
http://arxiv.org/abs/2310.01254
We investigate logics and classes of problems below Fagin's existential second-order logic (ESO) and above Feder and Vardi's logic for constraint satisfaction problems (CSP), the so called monotone monadic SNP without inequality (MMSNP). It is known
Externí odkaz:
http://arxiv.org/abs/2305.04234
Autor:
Barsukov, Alexey, Roy, Bodhayan
An interval graph has interval count $\ell$ if it has an interval model, where among every $\ell+1$ intervals there are two that have the same length. Maximum Cut on interval graphs has been found to be NP-complete recently by Adhikary et al. while d
Externí odkaz:
http://arxiv.org/abs/2203.06630
Publikováno v:
In Theoretical Computer Science 29 July 2024 1007
A trigraph is a graph where each pair of vertices is labelled either 0 (a non-arc), 1 (an arc) or $\star$ (both an arc and a non-arc). In a series of papers, Hell and co-authors proposed to study the complexity of homomorphisms from graphs to trigrap
Externí odkaz:
http://arxiv.org/abs/2107.13809
Autor:
Barsukov, Alexey
Publikováno v:
Computational Complexity [cs.CC]. Université Clermont Auvergne, 2022. English. ⟨NNT : 2022UCFAC092⟩
Computational Complexity [cs.CC]. Université Clermont Auvergne (UCA), 2022. English. ⟨NNT : ⟩
Computational Complexity [cs.CC]. Université Clermont Auvergne (UCA), 2022. English. ⟨NNT : ⟩
A subset of NP is said to have a dichotomy if it contains problem that are either solvable in P-time or NP-complete. The class of finite Constraint Satisfaction Problems (CSP) is a well-known subset of NP that follows such a dichotomy. The complexity
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::3150e376dbd01289be9303f782460249
https://theses.hal.science/tel-04100704
https://theses.hal.science/tel-04100704
Publikováno v:
Proceedings of the International Multidisciplinary Scientific GeoConference SGEM. 2019, Vol. 19 Issue 1, p667-673. 7p.
Autor:
Sharafullin, Kharis K.1, Barsukov, Alexey K.2, Kuznetsov, Alexandr I.2, Nesterova, Olga Y.2, Trebukh, Olga S.2
Publikováno v:
Proceedings of the International Multidisciplinary Scientific GeoConference SGEM. 2019, Vol. 19 Issue 1, p155-161. 7p.
Autor:
Vladimir Vladimirovich Bekezin, Korotkaya Natalia, Kozlova Lyudmila V., Olga Vladimirovna Peresetskaya, Barsukov Alexey V.
Publikováno v:
Medical news of the North Caucasus. 17
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5c1b1c16b4e7621c8ca39ff5f5592dc3
https://doi.org/10.14300/mnnc.2022.17060
https://doi.org/10.14300/mnnc.2022.17060