Zobrazeno 1 - 10
of 49
pro vyhledávání: '"Döcker, Janosch"'
Autor:
Döcker, Janosch, Linz, Simone
Rooted phylogenetic networks are used by biologists to infer and represent complex evolutionary relationships between species that cannot be accurately explained by a phylogenetic tree. Tree-child networks are a particular class of rooted phylogeneti
Externí odkaz:
http://arxiv.org/abs/2408.17105
In comparison to phylogenetic trees, phylogenetic networks are more suitable to represent complex evolutionary histories of species whose past includes reticulation such as hybridisation or lateral gene transfer. However, the reconstruction of phylog
Externí odkaz:
http://arxiv.org/abs/2405.19587
Autor:
Döcker, Janosch, Linz, Simone
Recently, there has been a growing interest in the relationships between unrooted and rooted phylogenetic networks. In this context, a natural question to ask is if an unrooted phylogenetic network U can be oriented as a rooted phylogenetic network s
Externí odkaz:
http://arxiv.org/abs/2401.05611
Publikováno v:
Advances in Applied Mathematics, 152:102595, 2024
In the context of reconstructing phylogenetic networks from a collection of phylogenetic trees, several characterisations and subsequently algorithms have been established to reconstruct a phylogenetic network that collectively embeds all trees in th
Externí odkaz:
http://arxiv.org/abs/2211.06549
Autor:
Döcker, Janosch, Linz, Simone
Publikováno v:
In Theoretical Computer Science 1 January 2025 1023
Publikováno v:
In Advances in Applied Mathematics January 2024 152
Autor:
Döcker, Janosch
We show that Monotone 3-Sat remains NP-complete if (i) each clause contains exactly three distinct variables, (ii) each clause is unique, i.e., there are no duplicates of the same clause, and (iii), amongst the clauses, each variable appears unnegate
Externí odkaz:
http://arxiv.org/abs/1912.08032
Publikováno v:
Theoretical Computer Science, 822:72-91, 2020
The complexity of variants of 3-SAT and Not-All-Equal 3-SAT is well studied. However, in contrast, very little is known about the complexity of the problems' quantified counterparts. In the first part of this paper, we show that $\forall \exists$ 3-S
Externí odkaz:
http://arxiv.org/abs/1908.05361
Autor:
Darmann, Andreas, Döcker, Janosch
We consider simplified, monotone versions of Not-All-Equal 3-Sat and 3-Sat, variants of the famous Satisfiability Problem where each clause is made up of exactly three distinct literals. We show that Not-All-Equal 3-Sat remains NP-complete even if (1
Externí odkaz:
http://arxiv.org/abs/1908.04198
Publikováno v:
The Electronic Journal of Combinatorics, 28, Paper 1.8, 2021
Phylogenetic trees canonically arise as embeddings of phylogenetic networks. We recently showed that the problem of deciding if two phylogenetic networks embed the same sets of phylogenetic trees is computationally hard, \blue{in particular, we showe
Externí odkaz:
http://arxiv.org/abs/1901.06725