Results 1 to 10 of about 10,810 (183)
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
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 +2 more sources
Extension Complexity, MSO Logic, and Treewidth [PDF]
Discrete Mathematics & Theoretical Computer Science, 2020 We consider the convex hull $P_{\varphi}(G)$ of all satisfying assignments of a given MSO formula $\varphi$ on a given graph $G$. We show that there exists an extended formulation of the polytope $P_{\varphi}(G)$ that can be described by $f(|\varphi ...
Petr Kolman +2 more
doaj +3 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
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
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
An Algorithmic Metatheorem for Directed Treewidth [PDF]
, 2015 The notion of directed treewidth was introduced by Johnson, Robertson, Seymour and Thomas [Journal of Combinatorial Theory, Series B, Vol 82, 2001] as a first step towards an algorithmic metatheory for digraphs.
Oliveira, Mateus de Oliveira
core +2 more sources
Benchmarking treewidth as a practical component of tensor network simulations. [PDF]
PLoS ONE, 2018 Tensor networks are powerful factorization techniques which reduce resource requirements for numerically simulating principal quantum many-body systems and algorithms.
Eugene F Dumitrescu +5 more
doaj +2 more sources
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 +1 more source
The treewidth of 2-section of hypergraphs [PDF]
Discrete Mathematics & Theoretical Computer Science, 2021 Let $H=(V,F)$ be a simple hypergraph without loops. $H$ is called linear if $|f\cap g|\le 1$ for any $f,g\in F$ with $f\not=g$. The $2$-section of $H$, denoted by $[H]_2$, is a graph with $V([H]_2)=V$ and for any $ u,v\in V([H]_2)$, $uv\in E([H]_2)$ if ...
Ke Liu, Mei Lu
doaj +1 more source