8 citations · 23 across the 8 of their papers we have counts for
8 papers
Orientations without transitive arcs for cubic graphs and phylogenetic networks
Janosch Döcker, Simone Linz
An -orientation of an undirected graph is an acyclic digraph with a single source and a single sink that can be obtained from by assigning a direction to each e…
An even simpler hard variant of Not-All-Equal 3-SAT
Andreas Darmann, Janosch Döcker, Britta Dorn
We show that Not-All-Equal 3-Sat remains NP-complete when restricted to instances that simultaneously satisfy the following properties: (i) The clauses are given as the disjoint un…
On the existence of funneled orientations for classes of rooted phylogenetic networks
Janosch Döcker, Simone Linz
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 phy…
On simplified NP-complete variants of Not-All-Equal 3-Sat and 3-Sat
Andreas Darmann, Janosch Döcker
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 lit…
Placing quantified variants of 3-SAT and Not-All-Equal 3-SAT in the polynomial hierarchy
Janosch Döcker, Britta Dorn, Simone Linz +1
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 counterpart…
Displaying trees across two phylogenetic networks
Janosch Döcker, Simone Linz, Charles Semple
Phylogenetic networks are a generalization of phylogenetic trees to leaf-labeled directed acyclic graphs that represent ancestral relationships between species whose past includes…