Results 1 to 10 of about 1,438 (161)

Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics. [PDF]

Algorithms Mol Biol, 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.
Marchand B, Ponty Y, Bulteau L.
europepmc   +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 ...
Hans Raj Tiwary, Martin Koutecký, Petr Kolman   +2 more
doaj   +4 more sources

Treewidth-based algorithms for the small parsimony problem on networks. [PDF]

Algorithms Mol Biol, 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
Scornavacca C, Weller M.
europepmc   +2 more sources

Maximum-scoring path sets on pangenome graphs of constant treewidth. [PDF]

Front Bioinform
We 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.
Brejová B, Gagie T, Herencsárová E, Vinař T.   +3 more
europepmc   +2 more sources

Automated design of dynamic programming schemes for RNA folding with pseudoknots. [PDF]

Algorithms Mol Biol, 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.
Marchand B, Will S, Berkemer SJ, Ponty Y, Bulteau L.   +4 more
europepmc   +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.
Dumitrescu EF, Fisher AL, Goodrich TD, Humble TS, Sullivan BD, Wright AL.   +5 more
europepmc   +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, Vida Dujmović, Mehrnoosh Javarsineh, Pat Morin, David R. Wood   +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

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, Robert Hickingbotham, Tony Huynh, David R. Wood   +3 more
doaj   +1 more source

A note on domino treewidth [PDF]

Discrete Mathematics & Theoretical Computer Science, 1999
In [DO95], Ding and Oporowski proved that for every k, and d, there exists a constant c_k,d, such that every graph with treewidth at most k and maximum degree at most d has domino treewidth at most c_k,d.
Hans L. Bodlaender
doaj   +3 more sources