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 +5 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
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 +5 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
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
Planar and Minor-Free Metrics Embed into Metrics of Polylogarithmic Treewidth with Expected Multiplicative Distortion Arbitrarily Close to 1* [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2023 We prove that there is a randomized polynomialtime algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter $\varepsilon\gt$ 0, constructs an edge-weighted graph H and an embedding $\eta: V(G ...
Vincent Cohen-Addad +3 more
semanticscholar +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
A Single-Exponential Time 2-Approximation Algorithm for Treewidth [PDF]
IEEE Annual Symposium on Foundations of Computer Science, 2021 We give an algorithm, that given an n-vertex graph $G$ and an integer k, in time 2O(k)n either outputs a tree decomposition of $G$ of width at most 2k + 1 or determines that the treewidth of $G$ is larger than k.
T. Korhonen
semanticscholar +1 more source