Zobrazeno 1 - 10
of 17
pro vyhledávání: '"Lagodzinski, J. A. Gregor"'
Autor:
Bilò, Davide, Casel, Katrin, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Lagodzinski, J. A. Gregor, Schirneck, Martin, Wietheger, Simon
We combine ideas from distance sensitivity oracles (DSOs) and fixed-parameter tractability (FPT) to design sensitivity oracles for FPT graph problems. An oracle with sensitivity $f$ for an FPT problem $\Pi$ on a graph $G$ with parameter $k$ preproces
Externí odkaz:
http://arxiv.org/abs/2112.03059
We study the problem of counting the number of homomorphisms from an input graph $G$ to a fixed (quantum) graph $\bar{H}$ in any finite field of prime order $\mathbb{Z}_p$. The subproblem with graph $H$ was introduced by Faben and Jerrum [ToC'15] and
Externí odkaz:
http://arxiv.org/abs/2011.04827
Autor:
Behrendt, Lukas, Casel, Katrin, Friedrich, Tobias, Lagodzinski, J. A. Gregor, Löser, Alexander, Wilhelm, Marcus
We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymm
Externí odkaz:
http://arxiv.org/abs/1911.02453
Autor:
Casel, Katrin, Fischbeck, Philipp, Friedrich, Tobias, Göbel, Andreas, Lagodzinski, J. A. Gregor
We present fully polynomial approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as pol
Externí odkaz:
http://arxiv.org/abs/1905.03194
While many optimization problems work with a fixed number of decision variables and thus a fixed-length representation of possible solutions, genetic programming (GP) works on variable-length representations. A naturally occurring problem is that of
Externí odkaz:
http://arxiv.org/abs/1806.02112
For theoretical analyses there are two specifics distinguishing GP from many other areas of evolutionary computation. First, the variable size representations, in particular yielding a possible bloat (i.e. the growth of individuals with redundant par
Externí odkaz:
http://arxiv.org/abs/1805.10169
Many important graph theoretic notions can be encoded as counting graph homomorphism problems, such as partition functions in statistical physics, in particular, independent sets and colourings. In this article we study the complexity of $\#_p\mathsf
Externí odkaz:
http://arxiv.org/abs/1802.06103
Autor:
Behrendt, Lukas, Casel, Katrin, Friedrich, Tobias, Lagodzinski, J. A. Gregor, Löser, Alexander, Wilhelm, Marcus
Publikováno v:
Journal of Computer and System Sciences. 136:157-170
We generalize the tree doubling and Christofides algorithm, the two most common approximations for TSP, to parameterized approximations for ATSP. The parameters we consider for the respective parameterizations are upper bounded by the number of asymm
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::66de0929c28780f71e3e570d5e3db331
https://doi.org/10.1016/j.jcss.2023.03.007
https://doi.org/10.1016/j.jcss.2023.03.007
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.
We study the problem of counting the number of homomorphisms from an input graph $G$ to a fixed (quantum) graph $\bar{H}$ in any finite field of prime order $\mathbb{Z}_p$. The subproblem with graph $H$ was introduced by Faben and Jerrum [ToC'15] and
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8866681eecb9de6af3966662e0eaf9b8