Zobrazeno 1 - 10
of 148
pro vyhledávání: '"Flum, Jörg"'
It is well known [Lov\'asz, 67] that up to isomorphism a graph~$G$ is determined by the homomorphism counts $\hom(F, G)$, i.e., the number of homomorphisms from $F$ to $G$, where $F$ ranges over all graphs. Thus, in principle, we can answer any query
Externí odkaz:
http://arxiv.org/abs/2111.13269
Autor:
Chen, Yijia, Flum, Joerg
Let $\mathscr C$ be a class of finite and infinite graphs that is closed under induced subgraphs. The well-known {\L}o\'s-Tarski Theorem from classical model theory implies that $\mathscr C$ is definable in first-order logic (FO) by a sentence $\varp
Externí odkaz:
http://arxiv.org/abs/2008.00420
For every $q\in \mathbb N$ let $\textrm{FO}_q$ denote the class of sentences of first-order logic FO of quantifier rank at most $q$. If a graph property can be defined in $\textrm{FO}_q$, then it can be decided in time $O(n^q)$. Thus, minimizing $q$
Externí odkaz:
http://arxiv.org/abs/1704.03167
Autor:
Chen, Yijia, Flum, Joerg
We demonstrate some lower bounds for parameterized problems via parameterized classes corresponding to the classical ${\rm AC}^0$. Among others, we derive such a lower bound for all fpt-approximations of the parameterized clique problem and for a par
Externí odkaz:
http://arxiv.org/abs/1606.08014
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.
Autor:
Chen, Yijia, Flum, Jörg
Publikováno v:
In Information and Computation August 2019 267:116-134
Autor:
Flum, Joerg, Grohe, Martin
Publikováno v:
Logical Methods in Computer Science, Volume 1, Issue 1 (March 7, 2005) lmcs:2272
Most parameterized complexity classes are defined in terms of a parameterized version of the Boolean satisfiability problem (the so-called weighted satisfiability problem). For example, Downey and Fellow's W-hierarchy is of this form. But there are a
Externí odkaz:
http://arxiv.org/abs/cs/0502005
This collection of papers deal with challenges in disciplines such as complexity theory, games, algorithms and semi group theory and discuss current chellenges in this field.