Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
Title resolution pending
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
fields
cs.DS 2verdicts
UNVERDICTED 2representative citing papers
Maximum APD subset selection is polynomial-time for scanwidth at most 2, NP-hard for scanwidth 3, with an O(2^sw n) FPT algorithm and linear-time results when the induced network is reticulation-visible or has bounded invisible reticulations per biconnected component.
citing papers explorer
-
Exact and Heuristic Computation of the Scanwidth of Directed Acyclic Graphs
Introduces exact and FPT algorithms for computing the scanwidth of DAGs and phylogenetic networks, plus a heuristic with good practical performance.
-
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
Maximum APD subset selection is polynomial-time for scanwidth at most 2, NP-hard for scanwidth 3, with an O(2^sw n) FPT algorithm and linear-time results when the induced network is reticulation-visible or has bounded invisible reticulations per biconnected component.