Results 1 to 10 of about 5,860 (222)
Separating layered treewidth and row treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Layered treewidth and row treewidth are recently introduced graph parameters that have been key ingredients in the solution of several well-known open problems.
Prosenjit Bose +4 more
doaj +4 more sources
Treewidth-based algorithms for the small parsimony problem on networks [PDF]
Algorithms for Molecular Biology, 2022 Background Phylogenetic reconstruction is one of the paramount challenges of contemporary bioinformatics. A subtask of existing tree reconstruction algorithms is modeled by the Small Parsimony problem: given a tree T and an assignment of character-states
Celine Scornavacca, Mathias Weller
doaj +3 more sources
Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics [PDF]
Algorithms for Molecular Biology, 2022 Hard graph problems are ubiquitous in Bioinformatics, inspiring the design of specialized Fixed-Parameter Tractable algorithms, many of which rely on a combination of tree-decomposition and dynamic programming.
Bertrand Marchand +2 more
doaj +2 more sources
Tight Algorithms for Connectivity Problems Parameterized by Modular-Treewidth [PDF]
arXiv, 2023 We study connectivity problems from a fine-grained parameterized perspective. Cygan et al. (TALG 2022) obtained algorithms with single-exponential running time $\alpha^{tw} n^{O(1)}$ for connectivity problems parameterized by treewidth ($tw$) by introducing the cut-and-count-technique, which reduces connectivity problems to locally checkable counting ...
Falko Hegerfeld, Stefan Kratsch
arxiv +3 more sources
Embedding phylogenetic trees in networks of low treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2023 Given a rooted, binary phylogenetic network and a rooted, binary phylogenetic tree, can the tree be embedded into the network? This problem, called \textsc{Tree Containment}, arises when validating networks constructed by phylogenetic inference methods ...
Leo van Iersel +2 more
doaj +3 more sources
Automated design of dynamic programming schemes for RNA folding with pseudoknots [PDF]
Algorithms for Molecular Biology, 2023 Although RNA secondary structure prediction is a textbook application of dynamic programming (DP) and routine task in RNA structure analysis, it remains challenging whenever pseudoknots come into play.
Bertrand Marchand +4 more
doaj +2 more sources
Maximum-scoring path sets on pangenome graphs of constant treewidth [PDF]
Frontiers in BioinformaticsWe generalize a problem of finding maximum-scoring segment sets, previously studied by Csűrös (IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2004, 1, 139–150), from sequences to graphs.
Broňa Brejová +3 more
doaj +2 more sources
Edge-Cut Width: An Algorithmically Driven Analogue of Treewidth Based on Edge Cuts [PDF]
arXiv, 2022 Decompositional parameters such as treewidth are commonly used to obtain fixed-parameter algorithms for NP-hard graph problems. For problems that are W[1]-hard parameterized by treewidth, a natural alternative would be to use a suitable analogue of treewidth that is based on edge cuts instead of vertex separators.
Cornelius Brand +4 more
arxiv +2 more sources
Degree-3 Treewidth Sparsifiers [PDF]
arXiv, 2014 We study treewidth sparsifiers. Informally, given a graph $G$ of treewidth $k$, a treewidth sparsifier $H$ is a minor of $G$, whose treewidth is close to $k$, $|V(H)|$ is small, and the maximum vertex degree in $H$ is bounded. Treewidth sparsifiers of degree $3$ are of particular interest, as routing on node-disjoint paths, and computing minors seems ...
Chandra Chekuri, Julia Chuzhoy
arxiv +3 more sources
On the treewidths of graphs of bounded degree. [PDF]
PLoS ONE, 2015 In this paper, we develop a new technique to study the treewidth of graphs with bounded degree. We show that the treewidth of a graph G = (V, E) with maximum vertex degree d is at most [Formula: see text] for sufficiently large d, where C is a constant.
Yinglei Song, Menghong Yu
doaj +2 more sources