Results 1 to 10 of about 1,532 (205)
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 +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
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
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
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
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
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
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
Improved product structure for graphs on surfaces [PDF]
Discrete Mathematics & Theoretical Computer Science, 2022 Dujmovi\'c, Joret, Micek, Morin, Ueckerdt and Wood [J. ACM 2020] proved that for every graph $G$ with Euler genus $g$ there is a graph $H$ with treewidth at most 4 and a path $P$ such that $G\subseteq H \boxtimes P \boxtimes K_{\max\{2g,3\}}$. We improve
Marc Distel +3 more
doaj +1 more source