Zobrazeno 1 - 10
of 4 540
pro vyhledávání: '"Konrád, K."'
We consider the MIN-r-LIN(R) problem: given a system S of length-r linear equations over a ring R, find a subset of equations Z of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate within any constan
Externí odkaz:
http://arxiv.org/abs/2410.09932
Difference Logic (DL) is a fragment of linear arithmetics where atoms are constraints x+k <= y for variables x,y (ranging over Q or Z) and integer k. We study the complexity of deciding the truth of existential DL sentences. This problem appears in m
Externí odkaz:
http://arxiv.org/abs/2402.03273
Autor:
Dabrowski, Konrad K., Dross, François, Jeong, Jisu, Kanté, Mamadou Moustapha, Kwon, O-joung, Oum, Sang-il, Paulusma, Daniël
A graph $G$ contains a graph $H$ as a pivot-minor if $H$ can be obtained from $G$ by applying a sequence of vertex deletions and edge pivots. Pivot-minors play an important role in the study of rank-width. Pivot-minors have mainly been studied from a
Externí odkaz:
http://arxiv.org/abs/2311.04656
Autor:
Dabrowski, Konrad K., Jonsson, Peter, Ordyniak, Sebastian, Osipov, George, Pilipczuk, Marcin, Sharma, Roohani
Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP
Externí odkaz:
http://arxiv.org/abs/2305.13889
Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This pro
Externí odkaz:
http://arxiv.org/abs/2208.02732
Autor:
Bulteau, Laurent, Dabrowski, Konrad K., Köhler, Noleen, Ordyniak, Sebastian, Paulusma, Daniël
A homomorphism $f$ from a guest graph $G$ to a host graph $H$ is locally bijective, injective or surjective if for every $u\in V(G)$, the restriction of $f$ to the neighbourhood of $u$ is bijective, injective or surjective, respectively. The correspo
Externí odkaz:
http://arxiv.org/abs/2201.11731
The constraint satisfaction problem (CSP) has important applications in computer science and AI. In particular, infinite-domain CSPs have been intensively used in subareas of AI such as spatio-temporal reasoning. Since constraint satisfaction is a co
Externí odkaz:
http://arxiv.org/abs/2107.01428
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Publikováno v:
In European Journal of Combinatorics March 2024 117
Autor:
Dabrowski, Konrad K., Dross, François, Jeong, Jisu, Kanté, Mamadou Moustapha, Kwon, O-joung, Oum, Sang-il, Paulusma, Daniël
Publikováno v:
SIAM J. Discrete Math., 35(4):2922-2945, December 2021
Tree-width and its linear variant path-width play a central role for the graph minor relation. In particular, Robertson and Seymour (1983) proved that for every tree~$T$, the class of graphs that do not contain $T$ as a minor has bounded path-width.
Externí odkaz:
http://arxiv.org/abs/2008.00561