18 citations · 79 across the 28 of their papers we have counts for
4 papers · 1 filter
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…
New reduction rules for the tree bisection and reconnection distance
Steven Kelk, Simone Linz
Recently it was shown that, if the subtree and chain reduction rules have been applied exhaustively to two unrooted phylogenetic trees, the reduced trees will have at most 15k-9 ta…
Display sets of normal and tree-child networks
Janosch Doecker, Simone Linz, Charles Semple
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 phy…
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…